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: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
route = [[] for i in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    route[a-1].append(b)
    
for i in route[0]:
    if len(route) != 1:
        for j in route[i-1]:
            if j == N:
                print('POSSIBLE')
                sys.exit()
    else:
        if i == N:
            print('POSSIBLE')
            sys.exit()
                
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  a, b = map(lambda x: int(x)-1, input().split())
  G[a].append(b)

for v in G[0]:
  if nv in G[v]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
A, B = [0]*n, [0]*n
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] += 1
    if b == n:
        B[a-1] += 1

for i in range(m):
    if A[i] == 1 and B[i] == 1:
        ans = 'POSSIBLE'
        break
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
A, B = [0]*n, [0]*n
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] += 1
    if b == n:
        B[a-1] += 1

if sum(B) == 0:
    print(ans)
    exit()
else:
    for i in range(m):
        if A[i] == 1 and B[i] == 1:
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
P, M = ("POSSIBLE", "IMPOSSIBLE")
dic = {}
for _ in range(m):
    a, b = map(int, input().split())
    if dic.get(a) is None: dic[a] = [b]
    else: dic[a] = dic[a] + [b]
    if dic.get(b) is None: dic[b] = [a]
    else: dic[b] = dic[b] + [a]
if dic.get(n) is None: print(M)
arr = dic[n]
for i in arr:
    if 1 in dic[i]: print(P)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
sa={}
sb={}
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:
    sa.add(b)
  if b==n:
    ab.add(a)
print("INPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Runtime Error

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

a_n= []
b_n= []

for i in range(M):
  a,b= map(int,input().split())
  a_n.append(a)
  b_n.append(b)
  

i= 0
flag= 0

if(M== 1):
  print("IMPOSSIBLE")
else:
  while True:
    if(a_n[i]== 1):
      b= b_n[i]
      for j in range(i+ 1,M):
        if(a_n[j]== b and b_n[j]== N):
          print("POSSIBLE")
          flag= 1
          break
    elif(flag== 1):
      break
    elif(i== M- 1):
      print("IMPOSSIBLE")
      break
    i+= 1

Submission status: Runtime Error

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

from collections import defaultdict 
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q and cur <3:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
        cur = dist[b]
    return dist

d1 = dfs(1)
if d1[n] ==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

from collections import defaultdict 
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1 = dfs(1)
if dfs(n) <=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import collections

n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
print(s)#[[1, 2], [2, 3]]

q = collections.deque()
q.append(1)

for k in range(2):
    for j in range(len(q))
        tmp = q.pop()
        for i in s:
            if tmp in i:
                if tmp > i[0]:
                    q.append(i[0])
                else:
                    q.append(i[1])

if n in q:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
L = []
for _ in range(M):
    L.append(list(map(int, input().split())))

first = []
second = []
for a, b in L:
    if a == 1:
        first.append(b)
    if b == N:
        second.append(a)
print('POSSIBLE' if set(first) & set(second) else 'IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
temp=[]
for i in range(0,m):
  a,b=map(int,input().split()):
    if a==1:
      if b==n:
        print("POSSIBLE")
        break
      else:
        temp.append(b)
else:
  for i in range(0,len(b)):
    if temp[i]==n:
        print("POSSIBLE")

else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

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

s = []
g = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s.append(g)
    elif b == N:
        g.append(a)
    
ans = set(s) & set(g)

if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc068/submissions/12987221
# C - Cat Snuke and a Voyage
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

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

    for i in edge[0]:
        if n - 1 in set(edge[i]):
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


def resolve2():
    n, m = map(int, input().split())

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

    depth = [0 for _ in range(n)]

    def dfs(v, p, d):
        depth[v] = d
        for u in edge[v]:
            if u == p:
                continue
            dfs(u, v, d + 1)

    dfs(0, -1, 0)
    if depth[n - 1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve2()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve2():
    n, m = map(int, input().split())

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

    depth = [0 for _ in range(n)]

    def dfs(v, p, d):
        depth[v] = d
        for u in edge[v]:
            if u == p:
                continue
            dfs(u, v, d + 1)

    dfs(0, -1, 0)
    if depth[n - 1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve2()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
u=0
for i in range(M):
  a,b=list(map(int,input().split()))
for i in range(M):
  if a[i]==1:
    s=b[i]
    idxlist=[]
    for idx,val in enumerate(a):
      if val==s:
        idxlist.append(idx)
    for j in idxlist:
      if b[j]!=N:
        u+=1
if u==len(idxlist):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[]
B=[]
for i in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
u=0
k=A.count(1)
for i in range(M):
  if A[i]==1:
    s=B[i]
    t=A.index(B[i])
    if B[t]!=N:
      u+=1
if u==k:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[]
B=[]
C=[]
for i in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
u=0
k=A.count(1)
for i in range(M):
  if A[i]==1:
    s=B[i]
    t=A.index(B[i])
    if B[t]!=N:
      u+=1
if u==k:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
if len(one_li) == 0 or len(to_n_li) == 0:
    print('IMPOSSIBLE')
    exit()
for o in list(set(one_li)):
    index = bisect.bisect_left(to_n_li, o)
    #print(to_n_li,o,index)
    if to_n_li[index] == o:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import bisect
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
if len(one_li) == 0 or len(to_n_li) == 0:
    print('IMPOSSIBLE')
    exit()
for o in list(set(one_li)):
    index = bisect.bisect_left(to_n_li, o)
    print(to_n_li,o,index)
    if to_n_li[index] == o:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import bisect
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
for o in list(set(one_li)):
    index = bisect.bisect_left(to_n_li, o)
    if to_n_li[index] == o:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.append(b)
    elif b == N:
        nb.append(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
E = {i+1: [] for i in range(M)}
first = []
for m in range(M):
    a, b = lr()
    if b == N:
        first.append(a)
    E[a].append(b)
for f in first:
    if f in E[1]:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
AB = np.array([[0]*M]*M)

for i in range(M):
  a,b = map(int,input().split())
  AB[a-1][i] = b
for i in range(M):
  if AB[0][i] != 0:
    k = AB[0][i]-1
    for j in range(M):
      if AB[k][j] == N:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
graph = [[0*n] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

flag = False
for i in range(n):
    if graph[0][i] == 1:
        if graph[i][n-1] == 1:
            flag = True
            break
                
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
c = [False for i in range(199999)]
d = [False for i in range(199999)]
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		c[b] = True
	if b == n:
		d[a] = True
for i in range(199999):
	if c[i] and d[i]:
		print ("POSSIBLE")
		exit()
print ("IMPOSSIBLE")

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input())
c = set()
d = set()
for i in range(m):
    a, b = map(int, input())
    if a == 1:
        c.add(b)
    if b == n:
        d.add(a)
ans = "POSSIBLE" if len(c & d) else "IMPOSSIBLE"

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a,b = [0]*m
for i in range(m):
    a[i],b[i] = map(int,input().split())
c = []
d = []
for i in range(m):
    
    if a[i] == 1:
        c.append(b[i])
    if b[i][1] == n:
        d.append(a[i])
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:

# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E = map(int, input().split())
    r = 0
    g = [[] for i in range(V)]

    for i in range(E):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        d = 1
        g[s].append((d, t))
        g[t].append((d, s))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E = map(int, input().split())
    r = 0
    g = [[] for i in range(V)]

    for i in range(E):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        d = 1
        g[s].append((d, t))
        g[t].append((d, s))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 10

    if dijkstra(V, g, r)[-1]==2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


resolve()
    INF = 10 ** 10

    if dijkstra(V, g, r)[-1]==2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


resolve()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
for i in range(m):
  a[i],b[i]=map(int,input().split())
c=[0]*m
for i in range(m):
  if a[i]==1:
    c[b[i]-1] |= 1
  if b[i]==n:
    c[a[i]-1] |= 2
print("POSSIBLE" if max(c)==3 else "IMPOSSIBLE")

Submission status: Runtime Error

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)
 
ans="IMPOSSIBLE"
    
for i in first:
  if i in second:

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

first = edges[1]
# print(first)
for fr in first:
    if N in edges[fr]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")N,M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

first = edges[1]
# print(first)
for fr in first:
    if N in edges[fr]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())
g = np.zeros((n, n), dtype=np.int)
for _ in range(m):
    a, b = map(int, input().split())
    g[a-1, b-1] = 1
    g[b-1, a-1] = 1

res = 'IMPOSSIBLE'
for i in range(n):
    if g[n-1, i] == 0:
        continue
    if g[i, 0] == 1:
        res = 'POSSIBLE'
        break

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())
g = np.zeros((n, n), dtype=int)
for _ in range(m):
    a, b = map(int, input().split())
    g[a-1, b-1] = 1
    g[b-1, a-1] = 1

res = 'IMPOSSIBLE'
for i in range(n):
    if g[n-1, i] == 0:
        continue
    if g[i, 0] == 1:
        res = 'POSSIBLE'
        break

print(res)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N,M = map(int, input().split())

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

B.sort()
if len(B) > 0 and len(A) > 0:
    for a in A:
        if B[bisect.bisect_left(B, a)]==a:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N,M = map(int, input().split())

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

B.sort()
if len(B) > 0:
    for a in A:
        if B[bisect.bisect_left(B, a)]==a:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N,M = map(int, input().split())

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

B.sort()
for a in A:
    if B[bisect.bisect_left(B, a)]==a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s,t=set(),set()
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:t.add(b)
  if b==n:s.add(a)
if s%t:print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Runtime Error

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 and b != n:
    s.add(b)
  if a != 1 and b == n:
    t.add(a)
 
for x in a:
  if x in b:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

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 and b != n:
    s.add(b)
  if a != 1 and b == n:
    t.add(a)

if len(a&b) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix


n,m = map(int,input().split())

a_L,b_L = [],[]

for i in range(n):
    a,b = map(int,input().split())
    a_L.append(a)
    b_L.append(b)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)])
relaypoint = []
i = 0
while(ab[i][0] == 1):
  relaypoint.append(ab[i][1])
  i += 1
ab.sort(key = lambda ab:ab[1],reverse = True)
relaypoint = set(relaypoint)
x = len(relaypoint)
j = 0
flag = 0
while(ab[j][1] == n):
  if ab[j][0] in relaypoint:
    flag = 1
  j += 1
if flag == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)])
relaypoint = []
i = 0
while(ab[i][0] == 1):
  relaypoint.append(ab[i][1])
  i += 1
ab.sort(key = lambda ab:ab[1],reverse = True)
relaypoint = list(set(relaypoint))
x = len(relaypoint)
j = 0
flag = 0
while(ab[j][1] == n):
  if ab[j][0] in relaypoint:
    flag = 1
  j += 1
if flag == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)])
relaypoint = []
i = 0
while(ab[i][0] == 1):
  relaypoint.append(ab[i][1])
  i += 1
ab.sort(key = lambda ab:ab[1] reverse = True)
relaypoint = list(set(relaypoint))
x = len(relaypoint)
j = 0
flag = 0
while(ab[j][1] == 5):
  if ab[j][0] in relaypoint:
    flag = 1
if flag == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
Ton = [False]*n
Fr1 = [False]*n
for i in range(m):
    a, b = map(int, input().split())
    if b==n:
        Ton[a] = True
    if a==1:
        Fr1[b] = True

r = 'IMPOSSIBLE'
for i in range(m):
    if Ton[i]==Fr1[i]==True:
        r = 'POSSIBLE'
print(r)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def check(ship_dic :dict, passed :list, start :int, cnt_list :list):
    next_island = ship_dic[start] - set(passed)

    if start == len(ship_dic) or len(next_island) == 0:
        cnt_list += [passed] 
        return 1,passed
    
    cnt=0
    for i in next_island:
        next_passed = list(passed) + [i]
        res,res_list = check(ship_dic, next_passed, i, cnt_list)
        cnt += res
            
    return cnt, cnt_list

#-----
N,M=[int(i) for i in input().rstrip().split()]
ab_list=[[int(j) for j in input().split()] for i in range(M)]

#-----
ship_dic={ i: set() for i in range(1,N+1)}  # dict{ int: set() }

for a,b in ab_list:
    ship_dic.setdefault(a, set())
    ship_dic[a].add(b)
    ship_dic.setdefault(b, set())
    ship_dic[b].add(a)

#-----
cnt_list=[] 
ans=check(ship_dic, [1], 1, cnt_list)  # cnt_list に、全経路のlistが返ってくる

for x in cnt_list:
    if x[-1] == N and len(x) == 3:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
def solve():
    N, M = map(int, input().split())
    T = {}
    for i in range(M):
        a, b = map(int, input().split())
        if a not in T:
            T[a] = []
        T[a].append(b)
        if b not in T:
            T[b] = []
        T[b].append(a)
    # print(N, M, T)
    FROM_1 = set(T[1])
    TO_N = set(T[N])
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[[0,0]]*m
t=[0]*m
tc=0
a=False
f=0
for k in range(m):
  l[k]=list(map(int,input().split()))
l.sort()
for k in l:
  if k[0]!=1 & f==0:
    del t[tc:]
  if k[0]==1:
    t[tc]=k[1]
    tc+=1
  elif k[1]==n:
    if k[0] in t:
      a=True
      break
if a:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
hune = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[0])

for a,b in hune:
    if a == 1:
        for c,d in hune:
            if c == b and d == N:
                print('POSSIBLE')
                return
    if a == 2:
        break
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
hune = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[0])

for a,b in hune:
    if a == 1:
        for c,d in hune:
            if c == b and d == N:
                print('Yes')
                return
    if a == 2:
        break
print('No')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(_m)]
cands = set(b if a == 1 else a for a, b in AB if a == 1 or b == 1)
if any(a in cands and b == n or b in cands and a == n for a, b in AB):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        s1.add(b)
    if b == N:
        s2.add(a)

for x in s1:
    if s2.count(x) >= 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        s1.append(b)
    if b == N:
        s2.append(a)

for x in s1:
    if s2.count(x) >= 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

from1 = [False]*N
toN = [False]*N
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1[max(a,b)-1]=True
  if a == N or b == N:
    toN[a-1 if a!= N else b-1]=True
cnt =0 
for i in range(M):
  cnt+=from1[i]&toN[i]
print("POSSIBLE" if cnt else "IMPOSSIBLE")

Submission status: Runtime Error

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

from1 = [False]*N
toN = [False]*N
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1[max(a,b)]=True
  if a == N or b == N:
    toN[a if a!= N else b]=True
cnt =0 
for i in range(M):
  cnt+=from1[i]&toN[i]
print("POSSIBLE" if cnt else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
first = []
second = []
for _ in range(M):
  a, b = map(int, input().split())
  if a == 1:
  	first.append(b)
  elif b == N:
    second.append(a)

ans = 0
for i in first:
  if i in second:
    ans = 1
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

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

q = []
for i in range(m):
	if info[i][0] == 1:
		q.append(info[i][1])
	else:
		t = i
		break

for j in range(t, m):
	if info[j][0] in q:
		if info[j][1] == n:
			print("POSSIBLE")
			break
else:
	print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
first = {}
second = {}
for i in range(m):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        first.add(b[i])
    if b[i] == n:
        second.add(a[i])


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

Submission status: Runtime Error

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

s = set()
g = set()

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        s.add(a)
    else b == N:
        g.add(a)

if set1 & set2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = int(input())
li = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b = map(int,input())
    a-=1
    b-=1
    li[a][b] = 1
    li[b][a] = 1

ans = False
for i in range(1,n-1):
    if li[0][i] and li[i][n-1]:
        ans = True
        break

if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
x=[]
y=[]
for i in range(M):
  a, b=map(int, input().split())
  if a==1:
    x.append(b)
  if b==1:
    x.append(a)
  if a==N:
    y.append(b)
  if b==N:
    y.append(a)
    
x.sort()
y.sort()
i=0
j=0
out='IMPOSSIBLE'
nx=len(x)
ny=len(y)
while i+j<nx+ny-1:
  if x[i]==y[j]:
    out='POSSIBLE'
    break
  elif x[i]>y[j]:
    j+=1
  else:
    i+=1
    
print(out)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
using namespace std;

int main(){
  int n,m;cin >> n >> m;
  vector<int> x;
  bool f=false;
  for(int i=0;i<m;i++){
    int a,b;cin >> a >>b;
    if(a==1){
      if(find(x.begin(),x.end(),b)!=x.end()){
        cout << "POSSIBLE" << endl;f=true;break;
      }else{
        x.push_back(b);
      }
    }
    if(b==n){
      if(find(x.begin(),x.end(),a)!=x.end()){
        cout << "POSSIBLE" << endl;f=true;break;
      }else{
        x.push_back(a);
      }
    }
  }
  if(!f){cout << "IMPOSSIBLE" << endl;}

}

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = {}
s_N = {}
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.add(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.add(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
tr=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if a!=1 and b!=n:
    continue
  tr[a].append(b)
  tr[b].append(a)
for i in range(n):
  if len(tr[i])==2:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
tr=[[] for i in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  if a!=1 and b!=n:
    continue
  tr[a].append(b)
  tr[b].append(a)
for i in range(m):
  if len(tr[m])==2:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split()))]
ab.sort()
medium = []
flag = 0
for i in range(m):
  if ab[i][0] == 1:
    medium.append(ab[i][1])
for j in range(m):
  if ab[j][0] in medium and ab[j][1] == n:
    flag = 1
if flag == 1:
  print("POSSIBLE")
else：
  print("IMPOSSIBLE")