//
问题 G: Cat Snuke and a Voyage
时间限制: 1.000 Sec 内存限制: 128 MB题目描述
In Takahashi Kingdom, there is an archipelago of "N islands", called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.
There are "M kinds of regular boat services" between these islands.
Each service connects two islands. The i-th service connects Island ai and Island bi.
Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N,
so he wants to know whether it is possible to go to Island N by using two boat services.
Help him.Constraints
3≤N≤200 000
1≤M≤200 000
1≤ai<bi≤N
(ai,bi)≠(1,N)
If i≠j, (ai,bi)≠(aj,bj).
输入
Input is given from Standard Input in the following format:
N M
a1 b1
a2 b2
:
aM bM
输出
If it is possible to go to Island N by using two boat services,
print POSSIBLE; otherwise, print IMPOSSIBLE.
样例输入 Copy
3 2
1 2
2 3
样例输出 Copy
POSSIBLEfor( auto i:v ) ____ for( auto &i:v )
//
#include<bits/stdc++.h>
using namespace std;// 3≤N≤200 000
const int MAXN=2e5+6;
vector<int> v[MAXN];int main()
{int n,m,a,b,flag;while( ~scanf("%d%d",&n,&m) ){for( int i=0;i<MAXN;i++ ) v[i].clear();while( m-- ){scanf("%d%d",&a,&b);v[a].push_back(b);}flag=0;for( auto i:v[1] ){for( auto j:v[i] ){if( j==n ) { flag=1; goto ans; } }}ans:if( flag ) printf("POSSIBLE\n");else printf("IMPOSSIBLE\n");}return 0;
}