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:
import sys
import heapq

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([1, b - 1])
        edge[b - 1].append([1, a - 1])

    # ダイクストラ法：O(ElogV)
    def dijkstra_heap(s):
        # 始点sから各頂点への最短距離
        d = [float("inf")] * n
        used = [True] * n  # True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            # まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    L = dijkstra_heap(n - 1)

    if L[0] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

first=L[0]
ok=False
for f in first:
    if N-1 in L[f]:
        ok=True
        break
if ok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    def bfs(G, s):
        dist = [-1 for _ in range(N)]
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
        return dist

    d = bfs(edge, 0)
    if 0 <= d[N-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if len(first & second):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    f = [[False]*2 for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            f[b][0] = True
        if b == n:
            f[a][1] = True
    ans = "IMPOSSIBLE"
    for i in range(1, n+1):
        if f[i][0] and f[i][1]:
            ans = "POSSIBLE"
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)

for new_v in G[0]:
    if n in G[new_v - 1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

G = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

for i in G[1]:
    for j in G[i]:
        if j == N:
            print ('POSSIBLE')
            exit()

print ('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ship = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        ship[a].append(b)
        ship[b].append(a)
    for i in range(1, n - 1):
        if 0 in ship[i] and n - 1 in ship[i]:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = [False]*n
b = [False]*n
for i in range(m):
    left, right = map(int, input().split())
    if left == 1:
        b[right-1] = True
    if right == n:
        a[left-1] = True

ans = 'IMPOSSIBLE'
for i in range(n):
    if a[i] == True and b[i] == True:
        ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
to = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
# print(to)
for i in range(len(to[0])):
    if n-1 in to[to[0][i]]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
froms = []
tos = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        froms.append(b)
    else:
        if not tos.get(a) and b == n:
            tos[a] = True
for f in froms:
    if tos.get(f) and tos[f]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
n,m = ma()
st = [False]*(n+1)
goal = [False]*(n+1)
for i in range(m):
    a,b = ma()
    if a==n:
        goal[b] =True
    if b==n:
        goal[a] =True
    if a==1:
        st[b] = True
    if b==1:
        st[a] = True
f = False
for i in range(1,n+1):
    if st[i] and  goal[i]:
         f=True
print("POSSIBLE") if f else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
n,m = ma()
tr = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
f = False
for i in tr[0]:
    for s in tr[i]:
        if s==n-1:
            f =True
print("POSSIBLE") if f else print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from_1 = 0
to_N = 0
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1 |= 1 << b
    if b == N:
        to_N |= 1 << a
print("POSSIBLE" if from_1 & to_N else "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)
	if y==N:
		G.append(x)
if S==[] or G==[]:
	print("IMPOSSIBLE")
	exit()
S=set(S)
G=set(G)
T=len(S)+len(G)
k=len(G)
S=list(S)
G=list(G)
for i in range(k):
	S.append(G[i])
U=len(set(S))
if T!=U:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N, M = map(int, readline().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        path[a].append(b)
        path[b].append(a)
    if set(path[1])&set(path[N]):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

goto_N = [0]*N
from_1 = [0]*N

for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        from_1[b] = 1
    elif b == N:
        goto_N[a] = 1

for i in range(N):
    if goto_N[i] and from_1[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

set_land1 = set()
set_landN = set()
for i in range(M):
    if rows[i][0]==1 or rows[i][1]==1:
        set_land1.add(rows[i][0])
        set_land1.add(rows[i][1])
    elif rows[i][0]==N or rows[i][1]==N:
        set_landN.add(rows[i][0])
        set_landN.add(rows[i][1])

set_root = set_land1 - set_landN
ans = "POSSIBLE"
if len(set_land1) == len(set_root):
    ans = "IMPOSSIBLE"

print(ans)

Submission status: Accepted

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

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

ship = []
keiyu = []

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

keiyu = set(keiyu)
for a, b in ship:
    if (a in keiyu and b == 1) or (b in keiyu and a == 1):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
str_N = str(N)
g = {str(i): set() for i in range(1, N + 1)}
for _ in range(M):
    A, B = input().split()
    if A == '1' or B == str_N:
        g[A].add(B)
        g[B].add(A)

if g['1'].intersection(g[str_N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
g = {i: set() for i in range(1, N + 1)}
for _ in range(M):
    A, B = map(int, input().split())
    if A in (1, N) or B in (1, N):
        g[A].add(B)
        g[B].add(A)

if g[1].intersection(g[N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = {i: set() for i in range(1, N + 1)}
for _ in range(M):
    A, B = map(int, input().split())
    g[A].add(B)
    g[B].add(A)

if g[1].intersection(g[N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
x=[]
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    x.append(b)
  if b==N:
    x.append(a)
l=len(x)
if len(set(x))==l:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Accepted

Solution code:
def myAnswer(N:int,M:int,A:list,B:list) -> int:
   dic = {key:[] for key in range(1,N+1)}
   for a,b in zip(A,B):
      dic[a].append(b)
   for i in dic[1]:
      for value in dic[i]:
         if(N == value):
            return "POSSIBLE"
   else:
      return "IMPOSSIBLE"

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = []
   B = []
   for _ in range(M):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)
   print(myAnswer(N,M,A[:],B[:]))
if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

for v in G[0]:
    if N-1 in G[v]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    q = [0]
    for _ in range(2):
        q2 = []
        while q:
            i = q.pop()
            for j in g[i]:
                q2.append(j)
        q = q2
    if n-1 in q:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append((1, b-1))
        edge[b-1].append((1, a-1))
    from heapq import heappop, heappush

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    dist = dijkstra(edge, 0)
    if dist[N-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

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

for v in G[0]:
    if n in G[v - 1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

G = [tuple(map(int, input().split())) for _ in range(M)]
G.sort(key = lambda x: x[0])

check = [False] * (N + 1)

for a, b in G:
    if a == 1:
        check[b] = True
    else:
        if check[a] and b == N:
            print ('POSSIBLE')
            exit()

print ('IMPOSSIBLE')

Submission status: Accepted

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

#初期値が0の辞書
from collections import defaultdict
tree = defaultdict(lambda: []) 

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

    tree[a].append(b)
    tree[b].append(a)

for item in tree[1]:
    if n in tree[item]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lone = [0]*n
ln = [0]*n
for i in range(m):
    a, b = map(int, input().split())
    if a==1: lone[b-1] = 1
    if b==1: lone[a-1] = 1
    if a==n: ln[b-1] = 1
    if b==n: ln[a-1] = 1
cant = True
for i in range(n):
    if lone[i] and ln[i]: cant = False
if cant: print("IMPOSSIBLE")
else: print("POSSIBLE")

Submission status: Accepted

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

for i in graph[0]:
    if n-1 in graph[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
sa = set()
sb = set()
for a,b in AB:
    if a==1:
        sa.add(b)
    if b==N:
        sb.add(a)
s = sa & sb
print('POSSIBLE' if len(s) else 'IMPOSSIBLE')

Submission status: Accepted

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

edges =[set() for _ in range(N + 1)]
one = set()
for _ in range(M):
    fr, to = map(int, input().split())
    edges[fr].add(to)
    edges[to].add(fr)
    if fr == 1:
        one.add(to)
    if to == 1:
        one.add(fr)

for fr in one:
    if N in edges[fr]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

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

#%%
flag = False
for r1 in route[1]:
    if n in route.get(r1, []):
        flag = True
        break

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
s=set();t=set();
for i in range(M):
  a,b=list(map(int,input().split()))
  if(a==1):
    s.add(b)
  if(b==N):
    t.add(a)
print("POSSIBLE"if s&t else"IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections


n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i 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 edge[i]:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
fune = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    fune[a-1].append(b-1)
    fune[b-1].append(a-1)
res = "IMPOSSIBLE"
for i in fune[0]:
    if n-1 in fune[i]:
        res = "POSSIBLE"
        break
print(res)

Submission status: Accepted

Solution code:
def main():
    n, m = list(map(int, input().split()))
    root_start = []
    root_goal = []
    ans = {}
    for i in range(m):
        li = list(map(int, input().split()))
        if li[0] == 1:
            ans.setdefault(li[1], 0)
            ans[li[1]] += 1
        elif li[1] == n:
            ans.setdefault(li[0], 0)
            ans[li[0]] += 1
    flg = False
    for k in ans:
        if ans[k] >= 2:
            flg = True

    print('POSSIBLE') if flg else print('IMPOSSIBLE')



if __name__ == '__main__':
    main()

Submission status: Accepted

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

set_1=set()
set_n=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    set_1.add(b)
  if b==N:
    set_n.add(a)
    
#print(set_1,set_n)
for x in set_1:
  if x in set_n:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
a=[0]*n
for i in range(m):
  if l[i][0]==1:
    a[l[i][1]]+=1
  elif l[i][1]==n:
    a[l[i][0]]+=1
for i in range(n):
  if a[i]==2:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
paths = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    paths[a - 1].append(b - 1)
for i in paths[0]:
    if n - 1 in paths[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    query = [ [int(a) for a in input().split()] for i in range(M)]
    query.sort(key=lambda x : x[0])
    mid = set()

    possible = False
    for q in query:
        a = q[0]
        b = q[1]

        if a == 1:
            mid.add(b)

        if b == N:
            if a in mid:
                possible = True
                break
    if possible:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
if __name__ == "__main__":
    main()

Submission status: Accepted

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

if iki.isdisjoint(nori):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
if len(set(graph[1]).intersection(set(graph[n]))) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:

def resolve():
    n,m = map(int, input().split())
    d = {}
    for i in range(m):
        a,b = map(int, input().split())
        if a not in d:
            d[a] = {}
        if b not in d:
            d[b] = {}
        d[a][b] = d[b][a] = 1

    if 1 not in d or n not in d:
        print('IMPOSSIBLE')
        return

    for a in d[1].keys():
        if a in d[n]:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

if len(set(ans)) != len(ans):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

se1 = set()
se2 = set()

for a,b in AB:
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
if se:
  ans = 'POSSIBLE'
else:
  ans = 'IMPOSSIBLE'
print(ans)

Submission status: Accepted

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

se1 = set()
se2 = set()

for a,b in AB:
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
	n, m = map(int, input().split())
	v = [[] for i in range(n+1)]
	for i in range(m):
		a, b = list(map(int, input().split()))
		v[a].append(b)
	ans = 'IMPOSSIBLE'
	for i in range(len(v[1])):
		if n in v[v[1][i]]:
			ans = 'POSSIBLE'
			break
	print(ans)
resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [set() for i in range(N + 1)]

for i in range(M):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

for a in G[1]:
    if a in G[N]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

for i in voya[0]:
    if N-1 in voya[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
from1 = []
to_n = []
for i in range(m):
    if ab[i][0] == 1:
        from1.append(ab[i][1])
    if ab[i][1] == n:
        to_n.append(ab[i][0])
from1.sort()
to_n.sort()
'''
for i in range(len(from1)):
    if from1[i] in to_n:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')
二分探索で実装できそう
'''
def bisearch(data,value):#data:ソート済みリスト  value:調べる値
  left = 0
  right = len(data) - 1
  while left <= right:
    mid = (left + right)//2
    if data[mid] == value:
      return mid
    elif data[mid] < value:
      left = mid + 1
    else:
      right = mid - 1
  return -1
for i in range(len(from1)):
    if bisearch(to_n,from1[i]) != -1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Submission status: Accepted

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

res=s&t
if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=tuple(tuple(map(int,input().split())) for _ in range (m))
s=set()
t=set()
for i in range(m):
    if 1 in p[i]:
        s.add(p[i][0])
        s.add(p[i][1])
    if n in p[i]:
        t.add(p[i][0])
        t.add(p[i][1])
res=s&t
if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
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)
ll = len(set(one_li) & set(to_n_li))
if ll == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = [0] * n
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s[b-1] = 1
    else: break
for A, B in AB:
    if B == n:
        if s[A-1] == 1:
            ans = "POSSIBLE"
    else: break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
from1_ls = []
togoal_ls = []
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        from1_ls.append(b)
    if b == n:
        togoal_ls.append(a)
set_from = set(from1_ls)
set_to = set(togoal_ls)
intersection = set_from & set_to
ans = 'IMPOSSIBLE'
if intersection:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [0 for i in range(n)]
e = [0 for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s[y] = 1
    elif y == n:
        e[x] = 1
flag = False
for i in range(n):
    if s[i] == 1 and e[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
N, M = map(int, readline().split())
x = set()
y = set()
for _ in range(M):
    a, b = map(int, readline().split())
    if a == 1:
        x.add(b)
    if b == N:
        y.add(a)
print('POSSIBLE' if x & y else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
f = [False] * N
s = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1

    if a == 0:
        f[b] = True
    if b == N -1:
        s[a] = True

ok = False
for i in range(N):
    if f[i] & s[i]:
        ok = True

print("POSSIBLE" if ok else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n,m = na()
g = [[] for i in range(n)]
for i in range(m):
    a,b = na()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

for i in g[0]:
    if n-1 in g[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

for i in path[0]:
    if n-1 in path[i]:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edges=[set() for i in range(n+1)]
for i in range(m):
	a,s=map(int,input().split())
	edges[a].add(s)
	edges[s].add(a)
for i in range(2,n):
	if i in edges[1] and i in edges[n]:
		print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

a = [0]*m
b = [0]*m
checks = [0]*n
checkg = [0]*n
for i in range(m):
    a[i],b[i] = map(int,input().split())
    if a[i]== 1:
        checks[b[i]]=1
    if b[i]== n:
        checkg[a[i]]=1
ans = 0
for i in range(n):
    if checks[i] == checkg[i] == 1:
        ans = 1
if ans :
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [[-1] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if ab[a-1][-1] == -1:
        ab[a-1][-1] = b-1
    else:
        ab[a-1].append(b-1)
flg = False
for i, mid in enumerate(ab[0]):
    if n-1 in ab[mid]:
        flg = True
        break

if flg :print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
r=[set() for i in range(n+1)]
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:
        r[ai].add(bi)
        r[bi].add(ai)

if len(r[1]&r[n])==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#r=[[] for i in range(n+1)]
r=[set() for i in range(n+1)]
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:
#        r[ai].append(bi)
#        r[bi].append(ai)
        r[ai].add(bi)
        r[bi].add(ai)
yn=""
for i in range(2,n):
    if (i in r[1]) and (i in r[n]):
        print("POSSIBLE")
        yn="POSSIBLE"
        break
if yn=="":
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
#print(G)

temp_list = G[0]
for next in temp_list:
    if n in G[next - 1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')