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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(set(x+y)):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cont_1 = set()
cont_n = set()

for ab in AB:
  a, b = ab
  if 1 in ab:
    cont_1.add(a)
    cont_1.add(b)
  if n in ab:
    cont_n.add(a)
    cont_n.add(b)

if cont_1 & cont_n:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
you=[]
other={i:False for i in range(n+1)}
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        you.append(b)
    elif b==n:
        other[a]=True
flag=False
for some in you:
    if other[some]:
        flag=True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
data = [list(map(int, input().split())) for _ in range(m)]
start = set(i[1] for i in data if i[0] == 1)
goal = set(j[0] for j in data if j[1] == n)

if start & goal:
    print('POSSIBLE')
else:
    print('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:
      sb.add(b)
    if b==N:
      sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=[0]*N
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        if a==0 or b==0:
            S[a+b]+=1
        if a==N-1 or b==N-1:
            S[a+b-(N-1)]+=1
            
    f=0
    for i in range(N):
        if S[i]==2:
            f=1
            
    if f==1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
        

main()

Submission status: Accepted

Solution code:
#068_C
n,m=map(int,input().split())
s1=set()
sn=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        s1.add(b)
    if b==n:
        sn.add(a)
print('POSSIBLE' if len(s1&sn) else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
def solve():
    N, M, *AB = map(int, open(0).read().split())
    FROM_1 = set()
    TO_N = set()
    for i in range(M):
        a, b = AB[2*i], AB[2*i + 1]
        if a == 1:
            FROM_1.add(b)
        elif a == N:
            TO_N.add(b)
        if b == 1:
            FROM_1.add(a)
        elif b == N:
            TO_N.add(a)
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
   solve()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
ab = [0 for _ in range(n+2)]

for _ in range(m):
    a, b = map(int, input().split())
    if a==1:
        ab[b] += 1
        continue
    elif b == n:
        ab[a] += 1
        continue
if max(ab) == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

if len(set(to_c) & set(fm_c)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
lst = [set() for i in range(N+1)]
for i in range(M):
    a,b = list(map(int,input().split()))
    lst[a].add(b)

for intermediate in lst[1]:
    if N in lst[intermediate]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

x = x.intersection(y)

if len(x)!=0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    FROM_1 = set()
    TO_N = set()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            FROM_1.add(b)
        elif a == N:
            TO_N.add(b)
        if b == 1:
            FROM_1.add(a)
        elif b == N:
            TO_N.add(a)
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Submission status: Accepted

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 = T[1]

    for f in FROM_1:
        if N in T[f]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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 = T[1]

for f in FROM_1:
    if N in T[f]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
p = [[int(i) for i in input().split()] for _ in range(m)]
a = []
for x in p:
    if x[0] == 1:
        a.append(x[1])

b = []
for x in p:
    if x[1] == n:
        b.append(x[0])
if set(a) & set(b):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[0,0]]*m
at=[0]*m
bt=[0]*m
atc=0
btc=0
a=False

f=0
for k in range(m):
  ln=list(map(int,input().split()))
  if ln[0]==1:
    at[atc]=ln[1]
    atc+=1
  elif ln[1]==n:
    bt[btc]=ln[0]
    btc+=1
del at[atc:]
del bt[btc:]
at.sort()
bt.sort()
c=list(set(at)^set(bt))
if len(c)!=(atc+btc):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m =map(int,input().split())
s = []
e = []
for i in range(m):
    a,b = map(int,input().split())
    if a ==1:
        s.append(b)
    if b == n:
        e.append(a)
if set(s)&set(e):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

one2 = set()
toN = set()

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

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

    if b == N:
        toN.add(a)

inter = one2 & toN

if len(inter) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

if len(set(A) & set(B)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())

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

def bfs(cur, pre, d):
    stack = deque([[cur, pre, d]])
    while stack:
        cur, pre, d = stack.popleft()
        if cur == n-1:
            return True
        for e in E[cur]:
            if e != pre and d < 2:
                stack.append([e, cur, d+1])
    return False

if bfs(0, -1, 0):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

edges=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
def dfs(cnt,v,before=-1):
    if cnt>=2:
        return False
    ans=False
    for to in edges[v]:
        if to!=before:
            if to==n-1:
                return True
            else:
                ans|=dfs(cnt+1,to,v)
    return ans

if dfs(0,0):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
p = [[int(i) for i in input().split()] for _ in range(m)]
a = []
for x in p:
    if x[0] == 1:
        a.append(x[1])

b = []
for x in p:
    if x[1] == n:
        b.append(x[0])
if set(a) & set(b):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
eage=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    eage[a-1].append(b-1)
    eage[b-1].append(a-1)
for e in eage:
    i_to_1=False
    i_to_n=False
    for ee in e:
        if ee==0:
            i_to_1=True
        if ee==n-1:
            i_to_n=True
        
        if i_to_1==True and i_to_n==True:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    islands, regular_boat = map(int, input().split())
    departure_from_island1 = []
    arrive_to_islandN = []
    for _ in range(regular_boat):
        start, final = map(int, input().split())
        if start == 1 and final == islands:
            continue
        elif start == 1:
            departure_from_island1.append(final)
        elif final == islands:
            arrive_to_islandN.append(start)
    print("POSSIBLE" if len(set(departure_from_island1) & set(arrive_to_islandN)) > 0 else "IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[]for i 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)
dist=[-1]*N
d=deque()
dist[0]=0
d.append(0)
while(len(d)!=0):
    v=d[0]
    d.popleft()
    for nv in G[v]:
        if(dist[nv]!=-1):
            continue
        dist[nv]=dist[v]+1
        d.append(nv)
if(dist[N-1]==2):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

q = deque([1])
visited = [False] * (n+1)
d = [0] * (n+1)

while q:
    now = q.popleft()
    visited[now] = True
    for i in graph[now]:
        if visited[i]:
            pass
        else:
            q.append(i)
            d[i] = d[now] + 1
if d[n] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lis1 = []
lis2 = []
ans = "IMPOSSIBLE"
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        lis1.append(b)
    else:
        lis2.append((a,b))
lis2 = set(lis2)        
for j in lis1:
    if (j,n) in lis2:
        ans = "POSSIBLE"
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = []
for i in range(m):
    a,b = map(int, input().split())
    L.append((a,b))

st,go = [],[]
for i in range(m):
    if 1 in L[i]:
        st.append(L[i][1])
    if n in L[i]:
        go.append(L[i][0])

if set(st)&set(go):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict


def check():
    N,M = map(int, input().split())
    B = []
    hune = defaultdict(list)
    for _ in range(M):
        a,b = map(int, input().split())
        if a == 1:
            B.append(b)
        hune[a].append(b)
    
    for b in B:
        for goal in hune[b]:
            if goal == N:
                print('POSSIBLE')
                return
    print('IMPOSSIBLE ')
    
check()

Submission status: Accepted

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

dep = []#一個目のの到着場所
arr = []#二回目のの出発場所
for i in range(n):
    if a[i][0]==1:
        dep.append(a[i][1])
    if a[i][1]==m:
        arr.append(a[i][0])
dep=set(dep)
arr=set(arr)
ans=dep & arr

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

Submission status: Accepted

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
e = []
for d in ab:
    if d[1] == N:
        c.append(d[0])
    elif d[0] == 1:
        e.append(d[1])

if len(set(c) & set(e)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

from_1 = set(b for a, b in AB if a == 1)
to_N = set(a for a, b in AB if b == N)
print('POSSIBLE' if from_1 & to_N else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
def solve():
    N,M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    ret = False
    for cod_1 in graph[1]:
        if N in graph[cod_1]:
            ret = True
            
    print('POSSIBLE' if ret else 'IMPOSSIBLE')
    
solve()

Submission status: Accepted

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: Accepted

Solution code:
import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))
# print(x)
p1 = set()
p2 = set()
for i in x:
    if i[0] == 1:
       p1.add(i[1])
    elif i[1] == n:
        p2.add(i[0])
# print(p1, p2)
if len(p1 & p2) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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())

ship_1 = []
ship_2 = []
for i in range(M):
    if a[i] == 1:
        ship_1.append(b[i])
    if b[i] == N:
        ship_2.append(a[i])

both = set(ship_1) & set(ship_2)
if len(both) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)
    
if len(set(d[1]) & set(d[n])) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a_set = set()
b_set = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        a_set.add(b)
    if b == N:
        b_set.add(a)

# print('a_set, b_set', a_set, b_set)
product = a_set & b_set
if len(product) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
ab = {}

for _ in range(m):
    a, b = map(int, input().split())
    if a not in ab:
        ab[a] = [b]
    else:
        ab[a].append(b)
ans = 0
for i in ab[1]:
    if i in ab:
        if n in ab[i]:
            ans = 1
        else:
            continue
    else:
        continue

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
d = defaultdict(int)

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

for i in li:
  if i[1] == N:
    d[i[0]] += 1

for i in li:
  if i[0] == 1 and d[i[1]] != 0:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

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)

if len(s1.intersection(s2)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

flag = False

def dfs(p, x, d):
	if d>=2:
		if x==N-1:
			global flag
			flag = True
		return

	for i in G[x]:
		if i==p:
			continue
		else:
			dfs(x,i,d+1)

dfs(-1,0,0)
print('POSSIBLE' if flag else 'IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

a = []
b = []
for i in l:
    if i[0] == 1:
        a.append(i[1])
    if i[1] == n:
        b.append(i[0])

print("POSSIBLE" if len(set(a)&set(b)) > 0 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
def takahasi(n , m , a):

    ans = "IMPOSSIBLE"
    list1n = []

    for i in range(m):
        if a[i][0] == 1 or a[i][1] == n:
            list1n.append(a[i][1] if a[i][0] == 1 else a[i][0])

    if len(list1n) != len(set(list1n)):
        ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for i in range(n)] #g[i]:点iに隣接している点のリスト
for i in range(m):
    x,y = map(int,input().split()) 
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

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())
start = []
goal = []
for i in range(m):
    a, b = map(int,input().split())
    if a == 1:
        start.append(b)
    if b == n:
        goal.append(a)
if set(start) & set(goal):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

from1 = [False]*max(N,M)
toN = [False]*max(N,M)
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1[a-1 if a!= 1 else 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: Accepted

Solution code:
N,M=map(int,input().split())
G = [list() for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
#O(M)
flag = False
for i in G[1]:
    if N in G[i]:
        flag = True
        break

if flag:
    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>b:
    a,b = b,a
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
#print(se1)
#print(se2)
answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque


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)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = deque([1])
while QUEUE:
    now = QUEUE.popleft()
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
d = {}
for _ 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

for v in d.values():
    if 1 in v and n in v:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = 0
dic = {str(i):0 for i in range(1,N)}
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        dic[str(b)] += 1
        if dic[str(b)] == 2:
            ans = 1
    if b == N:
        dic[str(a)] += 1
        if dic[str(a)] == 2:
            ans = 1
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
cand_1 = []
cand_n = []
for i in range(m):
  a,b = map(int,input().split())
  if a == 1:
    cand_1.append(b)
  elif b == n:
    cand_n.append(a)
flag = set(cand_1) & set(cand_n)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(M)]
sorted_lst = sorted(lst, key=lambda x: x[0])
ans = 'IMPOSSIBLE'
lst_1 = [0] * N
for i in sorted_lst:
  if (i[0] == 1):
    lst_1[i[1]-1] = 1
  elif (lst_1[i[0]-1] and i[1] == N):
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    a_, b_ = map(int, input().split())
    if a_ == 1 or a_ == n or b_ == 1 or b_ == n:
        a.append(a_)
        b.append(b_)

x_min=[]
x_max=[]
for i in range(len(a)):
    if a[i] == 1 or b[i] == 1:
        x_max.append(max(a[i], b[i]))
    if a[i] == n or b[i] == n:
        x_min.append(min(a[i], b[i]))
x = x_min + x_max
if len(x) == len(set(x)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
# coding: utf-8
N,M=map(int,input().split())
L=[]
B=[]
A=[]
flg=0
cnt=0
for i in range(M):
    a,b=list(map(int,input().split()))
    L.append([a,b])
    if a==1:
        B.append(b)
        cnt+=1
    elif b==N:
        A.append(a)
        
#print(L)
ans=[]
if len(set(A)&set(B))==0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
# coding: utf-8
N,M=map(int,input().split())
G=[[] for i in range(N+1)]

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

flg=False

near=[False for i in range(N+1)]

for i in range(len(G[1])):
    near[G[1][i]]=True

for i in range(len(G[N])):
    if near[G[N][i]]:
        flg=True

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

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
l = {}
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if b != 0:
        if a not in l.keys():
            l[a] = [b]
        else:
            l[a].append(b)
for k1 in l[0]:
    if k1 not in l.keys():
        continue
    for k2 in l[k1]:
        if k2 == N - 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
neighborof1 = set()
neighborofN = set()
for j in range(M):
    a, b = map(int, input().split())
    if a == 1:
        neighborof1.add(b)
    elif b == N:
        neighborofN.add(a)
flag = 0
if len(neighborof1) > len(neighborofN):
    for i in neighborofN:
        if i in neighborof1:
            flag = 1
            break
else:
    for k in neighborof1:
        if k in neighborofN:
            flag = 1
            break
if flag == 1:
    print("POSSIBLE")
else:
    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 > b : a, b = b, a
    if a == 1:
        s.add(b)
    if b == n:
        t.add(a)

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

Submission status: Accepted

Solution code:
arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

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

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
can = [[] for i in range(N + 1)]
for i in range(M):
  a, b = map(int, input().split())
  x = [a, b]
  if (1 in x) or (N in x):
    can[a].append(b)
    can[b].append(a)


for j in range(len(can[1])):
  k = can[1][j]
  if N in can[k]:
    print("POSSIBLE")
    quit()
    
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
a=len(D[-1])
b=len(D[0])
c=len(set(D[-1]+D[0]))
if a+b==c:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

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

starts = {}
goals = {}
for i in range(len(A)):
    s_num = A[i][0]
    g_num = A[i][1]
    if s_num == '1':
        starts[A[i][1]] = 0
    elif g_num == str(N):
        goals[A[i][0]] = 0

is_ok = False
for s in starts:
    if s in goals:
        is_ok = True
        break


# is_ok = False
# for j in range(len(start)):
#     for k in range(len(goal)):
#         if start[j][1] == goal[k][0]:
#             is_ok = True
#             break
#     if is_ok:
#         break

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

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, m, AB):
    g = [[] for _ in range(n)]
    for a, b in AB:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    q = deque(maxlen = n)
    q.append((0, 0))
    used = {0}
    while len(q) > 0:
        i, d = q.popleft()
        if d >= 2:
            break
        for c in g[i]:
            if c in used:
                continue
            if d == 1 and c == n - 1:
                return 'POSSIBLE'
            q.append((c, d + 1))
            used.add(c)
    return 'IMPOSSIBLE'

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Accepted

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

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


for i in rList[0]:
  if rList[i-1].count(n) > 0:
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(set)
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    d[a].add(b)


def solve(n, d):
    for a in d[1]:
        if n in d[a]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(solve(n, d))