Problem:


Score : 300 points

Problem Statement

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 a_i and Island b_i.

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 ≤ a_i < b_i ≤ N

(a_i, b_i) \neq (1, N)

If i \neq j, (a_i, b_i) \neq (a_j, b_j).

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

5 5
1 3
4 5
2 3
2 4
1 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
bs=[False for i in range(n)]
bt=[False for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 and (b!=n):
    bs[b-1]=True
  elif a!=1 and b==n:
    bt[a-1]=True
bool1=False
for i in range(1,n-1):
  if bs[i] and bt[i]:
    bool1=True
if bool1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

sa = set()  # 島1と便がある島
sb = set()  # 島Nと便がある島

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sa.add(b)
    if b == n:
        sb.add(a)

if len(sa & sb) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
li = []
numb = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        li.append(b)
    elif b == N:
        numb.append(a)
ans = set(li) & set(numb)
if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N , M = map(int, input().split())

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[0]*M
B=[0]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break
A=A[0:i]

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break
B=B[0:i]

if((len(A)==0)or(len(B)==0)):
    print("IMPOSSIBLE")
    exit()
if((max(A)<min(B))or(max(B)<min(A))):
    print("IMPOSSIBLE")
    exit()

A.sort()
B.sort()
i=0
j=0
while((i<len(A))and(j<len(B))):
    if A[i] == B[j]:
        print("POSSIBLE")
        exit()
    elif A[i] > B[j]:j+=1
    else:i+=1
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in ab:
    a,b=u
    data[a].append(b)
    data[b].append(a)
for u in data[1]:
    if n in data[u]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
g=[]
for i in range(m):
  x,y=map(int,input().split())
  if x==1:
    s.append(y)
  elif y==n:
    g.append(x)
s=set(s)
g=set(g)
z=s.intersection(g)
print('POSSIBLE' if len(z)>0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)],key=lambda x:x[0])
stop = set()
start = set()
for a,b in ab:
  if a == 1:
    stop.add(b)
  elif b == n:
    start.add(a)
print("POSSIBLE" if len(stop & start) > 0 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
a = []
b = []
ans = 'IMPOSSIBLE'
for _ in range(m):
    a1,b1 = map(int,input().split())
    a.append(a1)
    b.append(b1)
c = sorted(zip(a,b))
a.sort()
for i in range(m):
    if c[i][0] == 1:
        tmp1 = bisect.bisect_left(a,c[i][1])
        tmp2 = bisect.bisect_right(a,c[i][1])
        for j in range(tmp1,tmp2):
            if c[j][1] == n:
                ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    sys.setrecursionlimit(2000)
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1:
            d[b] += [1]
        if b == 1:
            d[a] += [1]
        if a == n:
            d[b] += [n]
        if b == n:
            d[a] += [n]
    for k, v in d.items():
        if len(v) == 2:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]

l = [[int(i) for i in input().split()] for _ in range(m)]

start = {i[1] for i in l if i[0] == 1}
end = {i[0] for i in l if i[1] == n}

if start & end:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]

l = [[int(i) for i in input().split()] for _ in range(m)]

start = [i[1] for i in l if i[0] == 1]
end = [i[0] for i in l if i[1] == n]

if set(start) & set(end):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
root1 = set()
root2 = set()
for i in range(M):
    ai,bi = map(int,input().split())
    if ai==1:
        root1.add(bi)
    if bi==N:
        root2.add(ai)
if set(root1) & set(root2):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        AB.append([a, b])

    F = [0] * N
    S = [0] * N
    
    for a, b in AB:
        if a == 1:
            F[b] = True
        if b == N:
            S[a] = True

    # print(F)
    # print(S)

    ans = 'IMPOSSIBLE'
    for i in range(N):
        if F[i] and S[i]:
            ans = 'POSSIBLE'
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        AB.append([a, b])

    first = set()
    second = set()

    for a, b in AB:
        if a == 1:
            first.add(b)
        elif b == N:
            second.add(a)

    # print(first, second)
    if first & second:
        print("POSSIBLE")
    else:
        print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        AB.append([a, b])

    A = [0] * (N + 3)

    for a, b in AB:
        # print(':', a, b)
        if a == 1:
            A[b] = 1

    # print(A)

    ans = 'IMPOSSIBLE'
    for a, b in AB:
        # print('::', a, b)
        if b == N:
            if A[a] == 1:
                ans = 'POSSIBLE'


    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readlines()
n, m = l[0].split()

from_1, to_n = set(), set()
for a, b in (l[i].split() for i in range(1, int(m)+1)):
    if a == '1': from_1.add(b)
    elif b == n: to_n.add(a)

print("POSSIBLE" if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readlines()
n, m = (int(x) for x in l[0].split())

from_1, to_n = set(), set()
for a, b in ((int(x) for x in l[i].split()) for i in range(1, m+1)):
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)

print("POSSIBLE" if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from collections import deque
l = deque(sys.stdin.readlines())
n, m = (int(x) for x in l[0].split())
l.popleft()

from_1, to_n = set(), set()
for a, b in deque((int(x) for x in l[i].split()) for i in range(m)):
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)

print("POSSIBLE" if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from collections import deque
l = deque(sys.stdin.readlines())
n, m = (int(x) for x in l[0].split())
l.popleft()

from_1, to_n = set(), set()
for a, b in ((int(x) for x in l[i].split()) for i in range(m)):
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)

print("POSSIBLE" if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
n, m, *ab = (int(x) for x in sys.stdin.read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] * 2): 
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")
# & は bloolean operator and ではなく set間で使われるoperator、 
# intersections が存在すればそれらのsetを返す。

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
first = []
second = []
for i in range(m):
    a,b = map(int, input().split())
    if a==1:
        first.append(b)
    elif b==n:
        second.append(a)
first_second = set(first)&set(second)
if len(first_second)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
n, m, *ab = map(int, sys.stdin.read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m, *ab = map(int, open(0).read().split())
from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] *2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 & to_n else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sa=set()
sb=set()
for i in range(m):
    a,b=map(int,input().split())
    if a==1:sa.add(b)
    if b==n:sb.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
#2次元配列
#a=[list(map(int,input().split())) for i in range(m)]

aa = []
bb = []
for i in range (m):
	a, b = map(int, input().split())
	if(a == 1):
		aa.append(b)
	if(b == n):
		bb.append(a)

if( len(set(aa) & set(bb)) == 0):
	print ("IMPOSSIBLE")
else:
	print ("POSSIBLE")

Submission status: Accepted

Solution code:
#068c
N,M = map(int, input().split())

regular_service_list = [set()for _ in range(N+1)]

for i in range(1,M+1):
    a,b = map(int, input().split())
    regular_service_list[a].add(b)
    regular_service_list[b].add(a)
    
common_island = regular_service_list[1]&regular_service_list[N]

if len(common_island)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
liners = {i: [] for i in range(1, n+1)}

for _ in range(m):
    a, b = map(int, input().split())
    liners[a].append(b)
    liners[b].append(a)

for l in liners[1]:
    if n in liners[l]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

AB.sort()
S1=[]
i=0
while AB[i][0]==1:
    S1.append(AB[i][1])
    i+=1
    if i>M-1:
        break

AB.sort(key=lambda x:x[1],reverse=True)
SN=[]
i=0
while AB[i][1]==N:
    SN.append(AB[i][0])
    i+=1
    if i>M-1:
        break

print(['IMPOSSIBLE','POSSIBLE'][len(set(S1)&set(SN))>=1])

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

next=set()
for a,b in AB:
  if a==1:
    next.add(b)
for a,b in AB:
  if a in next and b==n:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b = map(int, input().split())
  e[a].append((b, 1))
  e[b].append((a, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]
d = dijkstra(N, e)
if d.path(1, N) > 2:
  print("IMPOSSIBLE")
else: print("POSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
sa = set()
sb = set()
for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    sa.add(b)
  if b == n:
    sb.add(a)

if len(sa&sb) == 0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Accepted

Solution code:
#import math
#import copy
#import sys
#import bisect
#input = sys.stdin.readline
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))

def main():
    #x,y = map(int,input().split())	x=1,y=2
    #a = input().split()	a=['1','2','3',...,'n']
    #a = list(map(int,input().split()))	a=[1,2,3,4,5,...,n]
    #li = input().split('T')	FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    #複数行の「1 2 3 4」型の入力を一配列に
    #x = sorted([list(map(int, input().split())) for _ in range(n)])
    #ソート x.sort(key=lambda y:y[1])
    # print("Yes")  print("No")  x=[[0 for _ in range(n)] for _ in range(n)]
    n,m = map(int,input().split())
    ab = sorted([list(map(int, input().split())) for _ in range(m)])
    ab.sort()
    x=[n+2 for _ in range(n)]
    x[0]=0
    for i in range(m):
        x[ab[i][1]-1]=min(x[ab[i][0]-1]+1,x[ab[i][1]-1])
    if x[n-1]==2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

main()

Submission status: Accepted

Solution code:
N, M, *AB = map(int, open(0).read().split())
# print('N={0}, M={1}, AB={2}'.format(N, M, AB))
from_1, to_N = set(), set()
for a, b in zip(*[iter(AB)] *2):
#     print('a={0}, b={1}'.format(a,b))
    if a == 1:
        from_1.add(b)
    if b == N:
        to_N.add(a)
flg = from_1 & to_N
print("POSSIBLE" if flg else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    chains_list = list(map(string_to_int, inputs))
    chains = {i+1: set() for i in range(N)}
    for c in chains_list:
        chains[c[0]].add(c[1])
        chains[c[1]].add(c[0])

    if 1 not in chains:
        return "IMPOSSIBLE"
    hops = chains[1]

    for h in hops:
        if N in chains[h]:
            return "POSSIBLE"
    return "IMPOSSIBLE"


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str
import bisect

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ab = list(zip(a,b))
    ab.sort(key=lambda x: x[0])
    a.sort()

    for aabb in ab:
        if aabb[0] != 1:
            break 

        next_index = bisect.bisect_left(a,aabb[1])
        next_index2 = bisect.bisect_left(a,aabb[1]+1)

        for i in range(next_index,next_index2):
            if ab[i][1] == N:
                print(YES)
                return

    print(NO)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
out1=set()
inN=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        out1.add(b)
    elif b==N:
        inN.add(a)

print('POSSIBLE' if len(out1 & inN)>0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A,B=[0]*M,[0]*M
for i in range(M):
  A[i],B[i]=map(int,input().split())
X,Y=[0]*N,[0]*N
for i in range(M):
  if(A[i]==1):
    X[B[i]-1]=1
  elif(B[i]==N):
    Y[A[i]-1]=1
sum=0
for i in range(N):
  sum+=X[i]*Y[i]
if(sum):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
def main():
    N, M, *AB = map(int, open(0).read().split())
    from_1, to_N = set(), set()
    for a, b in zip(*[iter(AB)] * 2):
        if a == 1:
            from_1.add(b)
        if b == N:
            to_N.add(a)
    flg = from_1 & to_N  # intermediate point of both 1, N exists?
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
def main():
    N, M, *AB = map(int, open(0).read().split())
    sources, targets = set(), set()
    for a, b in zip(*[iter(AB)] * 2):
        if a == 1:
            sources.add(b)
        if b == N:
            targets.add(a)
    flg = sources & targets  # intermediate point of both 1, N exists?
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
import collections
table=collections.defaultdict(int)
table2=collections.defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    table[b]+=1
  if b==N:
    table2[a]+=1
for x in table:
  if x in table2:
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
from collections import defaultdict 
d=defaultdict(list)
from collections import deque 
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[0]*n 
vis=[0]*n 
vis[0]=1 
q=deque() 
q.append(0)
while q:
    t=q.popleft()
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            dist[i]=dist[t]+1 
            q.append(i)
print('POSSIBLE' if dist[n-1]==2 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
first=[]
second=[]
for m in range(M):
    a,b=map(int,input().split())
    if a==1:
        first.append(b)
    elif b==N:
        second.append(a)
first_and_second=set(first)&set(second)
if len(first_and_second)==0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    s = collections.defaultdict(list)
    e = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1:
            s[b]
        if b == 1:
            s[a]
        if a == n:
            e[b]
        if b == n:
            e[a]
    for v in s.keys():
        if v in e:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")



if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    G = [[] for i in range(N+1)]
    G_color = ['WHITE' for _ in range(N+1)]
    G_distance = [float('inf') for _ in range(N+1)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        G[a].append(b)
        G[b].append(a)

    def bfs(s):
        """
        G_color: BLACK if visited, GRAY if discovered, but will visit, WHITE
                 if not discovered
        G_distance: a distance from s to v when algorithm computed
        """
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    Q.append(v)
                    # distance <= 2 が探索し終わったら終わり
                    if G_distance[v] == 3:
                        return None
            G_color[u] = 'BLACK'
    bfs(1)
    if G_color[N] != 'WHITE' and G_distance[N] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC068 C - Cat Snuke and a Voyage
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,m = nm()
G = [[] for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# print(G)

for g in G:
    island_1toi = False
    island_iton = False
    for gg in g:
        if gg == 0:
            island_1toi = True
        if gg == n-1:
            island_iton = True

        if island_1toi == True and island_iton == True:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
AB.sort(key=lambda x:(x[0],x[1]))
#print(AB)

C =set()
for a,b in AB:
  if a == 1:
    C.add(b)
  elif b == N and a in C:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_ship = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  list_ship[a-1].append(b-1)
  list_ship[b-1].append(a-1)

same_island = set(list_ship[0]) & set(list_ship[-1])
if len(same_island) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import heapq
INFTY = 1e6
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
d = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,1)]
d[1] = 0
while heap:
    cur = heapq.heappop(heap)
    hist[cur[1]] = 1
    for x in G[cur[1]]:
        if hist[x]==0:
            if d[x]>cur[0]+1:
                d[x] = cur[0]+1
                heapq.heappush(heap,(d[x],x))
if d[N]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s1 = set()
e1 = set()
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s1.add(b)
    if b == N:
        e1.add(a)
if len(s1 & e1) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
root1 = set()
root2 = set()

for _ in range(m):
    a,b = map(int,input().split())
    if a==1:
        root1.add(b)
    if b ==n:
        root2.add(a)

for root in root1:
    if root in root2:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int, input().split())) for i in range(m)]
l.sort()
r=[]
q=[]
for i in range(m):
    if l[i][0]==1:
        r.append(l[i][1])
    elif l[i][1]==n:
        q.append(l[i][0])
if set(r)&set(q):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# C - Cat Snuke and a Voyage

N, M = map(int, input().split())
destination = [[] for _ in range(N)] # 島iから直接行ける島のリスト

for _ in range(M):
    a, b = map(int, input().split())
    destination[a-1].append(b-1)
    
for mid in destination[0]:
    if N-1 in destination[mid]:
        print("POSSIBLE")
        exit()
            
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
Ship = [list(map(int,input().split())) for i in range(m)]

Ship1 = []
Ship2 = []

for i in Ship:
    if i[0] == 1:
        Ship1 += [i[1]]
    elif i[1] == n:
        Ship2 += [i[0]]
if set(Ship1) & set(Ship2):#set型のShip1とShip2の積集合を求めて、もし積集合が存在するならばPOSSIBLE、存在しないならIMPOSSIBLEを表示させる
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
Ship = [list(map(int,input().split())) for i in range(m)]

Ship1 = []
Ship2 = []

for i in Ship:
    if i[0] == 1:
        Ship1 += [i[1]]
    elif i[1] == n:
        Ship2 += [i[0]]
if set(Ship1) & set(Ship2):#もし同じ値があったらPOSSIBLE、なかったらINPOSSIBLEと表示させる
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import bisect
def main():
    n,m=map(int,input().split(' '))
    mid=[]
    goal=[]
    for i in range(m):
        a,b=map(int,input().split(' '))
        if a==1:
            mid.append(b)
        if b==n:
            goal.append(a)
    mid = sorted(mid)
    for g in goal:
        i=bisect.bisect_left(mid,g)
        j=bisect.bisect_right(mid,g)
        if i != j:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def input():
    import sys
    return sys.stdin.readline().rstrip()


def main():
    import math
    import collections
    import itertools

    n, m = map(int, input().split())
    ships = collections.defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        ships[a].append(b)
        ships[b].append(a)
        
    for ship_1 in ships[1]:
        if n in ships[ship_1]:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
Ship = [list(map(int,input().split())) for i in range(m)]

Ship1 = []
Ship2 = []

for ship in Ship:
    if ship[0]==1:
        Ship1 += [ship[1]]
    elif ship[1]==n:
        Ship2 += [ship[0]]
if set(Ship1)&set(Ship2):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

l=[0]*(N+1)
temp=[]

for _ in range(M):
    a,b=map(int,input().split())
    l[a]=max(l[a],b)
    if a==1:
        temp.append(b)

for item in temp:
    if l[item]==N:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
S = set()
T = set()
for i in range(M):
    a, b = map(int,input().split())
    if a == 1:
        S.add(b)
    elif b == 1:
        S.add(a)
    elif a == N:
        T.add(b)
    elif b == N:
        T.add(a) 

if S.isdisjoint(T):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
all_cand = [tuple(map(int, input().split())) for _ in range(m)]

start_path_end = set([path[1] for path in all_cand if path[0]==1])
end_path_start = set([path[0] for path in all_cand if path[1]==n])

print('POSSIBLE' if start_path_end&end_path_start else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

tree=[[] for i in range(n)]
for i in l:
    tree[i[0]-1].append(i[1]-1)
    tree[i[1]-1].append(i[0]-1)

for i in tree:
    if 0 in i and n-1 in i:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

sx=0
gx=n-1

tree=[[] for i in range(n)]
for i in l:
    tree[i[0]-1].append(i[1]-1)
    tree[i[1]-1].append(i[0]-1)

dist=[-1 for i in range(n)]
dist[sx]=0

que=deque()
que.append(sx)

while que:
    x=que.popleft()

    if x==gx and dist[gx]==2:
        print('POSSIBLE')
        exit()
    elif x==gx and dist[gx]!=2:
        print('IMPOSSIBLE')
        exit()

    for j in tree[x]:
        if dist[j]==-1:
            que.append(j)
            dist[j]=dist[x]+1

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in root[0]:
        if N-1 in root[i]:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
shima1 = []
shimaN = []

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        shima1.append(b)
    if b == n:
        shimaN.append(a)

if len(set(shima1) & set(shimaN)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
d = [[] for _ in range(200001)]
for i in range(M):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

ans = 'IMPOSSIBLE'
for i in d[1]:
    if N in d[i]:
        ans = 'POSSIBLE'
        break

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = set()
r = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l.add(b)
    if b == n:
        r.add(a)
if len(l & r) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE ")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
n -= 1

ab = [[] for i in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)

for i in ab[0]:
    for j in ab[i]:
        if j == n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
route = [list(map(int, input().split())) for i in range(M)]

first = [a[1] for a in route if a[0] == 1]
second = [a[0] for a in route if a[1] == N]

ans = 'POSSIBLE' if set(first) & set(second) else 'IMPOSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edges = {tuple(map(int,input().split())) for _ in range(m)}
for i in range(2,n):
    if (1,i) in edges and (i,n) in edges:
        print("POSSIBLE")
        break
else:print("IMPOSSIBLE")