Problem:


Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

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

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

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

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

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

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

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

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

Sample Output 4

POSSIBLE

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



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a, b = [], []
    from_1 = set()
    to_n = set()
    for _ in range(m):
        x, y = map(int, input().split())
        if x == 1:
            from_1.add(y)
            continue
        if y == n:
            to_n.add(x)
            continue
    ans = from_1 & to_n
    if ans:
        return "POSSIBLE"

    return 'IMPOSSIBLE'


print(main())

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
from1 = [False]*(n+1)
toN = [False]*(n+1)
for _ in range(m):
    a, b = map(int,input().split())
    if a > b:
        a, b = b, a
    if a == 1:
        from1[b] = True
    if b == n:
        toN[a] = True
for i in range(n):
    if from1[i] and toN[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split(' '))
ferrys = [list(map(int, input().split(' '))) for _ in range(M)]
cand1to = []
candtoN = []
for f in ferrys:
    if f[0] == 1:
        cand1to.append(f[1])
    elif f[1] == 1:
        cand1to.append(f[0])
    elif f[0] == N:
        candtoN.append(f[1])
    elif f[1] == N:
        candtoN.append(f[0])

if set(cand1to) & set(candtoN) == set([]):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

for i in range(m):
  a, b = map(int, input().split())
  l[a].append(b)
def f():
  for i in l[1]:
    if n in l[i]:
      return 'POSSIBLE'
  
  return 'IMPOSSIBLE'
print(f())

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(m):
    island_set.add(tuple(map(int, input().split())))

for i in range(2, n):
    if (1, i) in island_set:
        if (i, n) in island_set:
            print("POSSIBLE")
            break

else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
a1, aN, b1, bN = set(), set(), set(), set()
for i in range(M):
    temp_a, temp_b = inpl()
    if temp_a == 1:
        a1.add(temp_b)
    elif temp_a == N:
        aN.add(temp_b)
    
    if temp_b == 1:
        b1.add(temp_a)
    elif temp_b == N:
        bN.add(temp_a)

if len(a1&bN)!=0 or len(aN&b1)!=0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

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

print('POSSIBLE' if len(s1&s2) else 'IMPOSSIBLE')

Submission status: Accepted

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

boolins =[]
for i in range(n):
    boolins.append(0)
    
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        boolins[xxx[1]] = boolins[xxx[1]] + 1
    elif xxx[1] == n :
        boolins[xxx[0]]=boolins[xxx[0]]+ 1
    else:
        None


if 2 in boolins:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = (int(i) for i in input().split())
a,b = [0 for i in range(m)],[0 for i in range(m)]
g = [[] for i in range(n)]
OK = False 
for i in range(m):
    a[i],b[i] = map(int, input().split())
    a[i]-=1
    b[i]-=1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
for i in range(m):
    if a[i]==0 and n-1 in g[b[i]]:
        OK = True
print('POSSIBLE' if OK else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[]
for j in range(M):
    x=list(map(int,input().split()))
    if N in x and 1 in x:
        print("POSSIBLE")
        exit()
    if N in x:
        x.remove(N)
        s+=x
    if 1 in x:
        x.remove(1)
        s+=x
if len(list(set(s)))!=len(s):
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

rou = [[] for i in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	rou[a-1].append(b-1)
	rou[b-1].append(a-1)
for i in rou[0]:
	for j in rou[i]:
		if j == n-1:
			print("POSSIBLE")
			exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def read_boats(n, m):
    boats = [[] for i in range(max(n, m) + 1)]
    for i in range(m):
        a, b = map(int, input().split())
        boats[a].append(b)
    return boats

def trip(n, boats):
    for origin in boats[1]:
        if n in boats[origin]:
            return('POSSIBLE')
    return('IMPOSSIBLE')


if __name__ == '__main__':
    n, m = map(int, input().split())
    boats = read_boats(n, m)
    print(trip(n, boats))

Submission status: Accepted

Solution code:
def c_cat_snuke_and_a_voyage(N, M, I):
    p = [False] * N  # 島1と島iに辺があるならTrue,なければFalse(0-indexed)
    q = [False] * N  # 島iと島Nに辺があるならTrue,なければFalse(0-indexed)
    for a, b in I:
        if a == 1:  # 出発地が島1なら
            p[b] = True
        elif b == N:  # 目的地が島Nなら
            q[a] = True
    ans = 'IMPOSSIBLE'
    for i in range(N):
        if p[i] and q[i]:
            ans = 'POSSIBLE'
            break  # 1つでもあればいい
    return ans

N,M = [int(i) for i in input().split()]
I = [[int(i) for i in input().split()] for j in range(M)]
print(c_cat_snuke_and_a_voyage(N, M, I))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#! /usr/bin/python3

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

a, b = [], []
ok = [False for x in range(n + 1)]

for i in range(m):
    x, y = map(int, input().split())
    a += [x]
    b += [y]
    if x == 1:
        ok[y] = True

for i in range(m):
    x, y = a[i], b[i]
    if ok[x] and y == n:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

for i in range(m):
  temp = list(map(int, input().split()))
  ship[temp[0]-1].append(temp)

for i in range(len(ship[0])):
  now = ship[0][i]
  if [now[1], n] in ship[now[1]-1]:
    flag = True
    break

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
from1 = set()
ton = set()
for i in range(M):
  l,r = map(int,input().split())
  if l == 1:
    from1.add(r)
  if r == N:
    ton.add(l)
if len(from1&ton) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
[n,m] = list(map(int,input().split(' ')))
L1 = [0]*n
Ln = [0]*n
i=0
while i < m:
    l0 = list(map(int,input().split(' ')))
    if l0[0] == 1:
        L1[l0[1]] = 1
    elif l0[1] == n:
        Ln[l0[0]] = 1
    i += 1
q = 0
while q < n:
    if L1[q] * Ln[q] == 1:
        print('POSSIBLE')
        q = 0
        break
    else:
        q += 1
if q != 0:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
li1=set()
lin=set()
for i in range(m):
  a,b=map(int,input().split())
  if(a==1):li1.add(b)
  elif(b==1):li1.add(a)
  elif(a==n):lin.add(b)
  elif(b==n):lin.add(a)
for i in li1:
  if(i in lin):
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans_1=[]
ans_2=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        ans_1.append(b)
    if b==n:
        ans_2.append(a)
if set(ans_1)&set(ans_2)!=set():#共通の要素があればpossible
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

s = []
g = []

for ship in ships:
    if ship[0] == 1:
        s.append(ship[1])
    if ship[1] == N:
        g.append(ship[0])

res = False

if not (len(s) == 0 or len(g) == 0):
    res = not set(s).isdisjoint(set(g))

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
goal = []

for ship in ships:
    if n in ship:
        goal.append(ship[0])
    elif 1 in ship:
        relay.append(ship[1])

res = False
if len(goal) == 0 or len(relay) == 0:
    print("IMPOSSIBLE")

else:
    print("IMPOSSIBLE" if not set(relay) & set(goal) else "POSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(m)]
B = []
C = []
for i in A:
    if 1 in i:
        B += i
B = set(B)
for i in A:
    a,b = i
    if a in B:
        C.append(b)
    elif b in B:
        C.append(a)
        
C = set(C)

if n in C or n in B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
g,l=input().split()
c=int(l)
a=[]
n=[]
m=[]

for i in range(c):
  i1,i2=input().split()
  a.append([i1,i2])
  if i1 =='1':
    n.append(i2)
  if i2 =='1':
    n.append(i1)
  if i1 ==g:
    m.append(i2)
  if i2 ==g:
    m.append(i1)

if list(set(m) & set(n)):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
route = [[] for i in range(n + 1)]
for j in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
for h in set(route[1]):
    for b in set(route[h]):
        if b == n:
            print("POSSIBLE")
            exit()
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

toN = list(filter(lambda x: N in x, AB))
toN = set([flatten for inner in toN for flatten in inner])
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = set([flatten for inner in frm_first for flatten in inner])

if toN & frm_first:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = []
d = []
flag = 0
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        c.append(b[i])
        if b[i] == N:
            flag = 1
    if b[i] == N:
        d.append(a[i])
        if a[i] == 1:
            flag = 1
e = set(c) | set(d)
if len(c) + len(d) == len(e):
    flag = 0
else:
    flag = 1

if flag == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

E = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    e = E.get(a, None)
    if e is None:
        e = []
    e.append(b)
    E[a] = e
    e = E.get(b, None)
    if e is None:
        e = []
    e.append(a)
    E[b] = e


def foo(E):
    for i in range(1, n):
        if i in E and 1 in E[i] and n in E[i]:
            return True
    return False

if foo(E):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

for i in range(len(A[0])):
    if len(A[A[0][i]]) is not 0:
        if N-1 in A[A[0][i]]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
q = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        p = P[i][1]
        if q < 0:
            if i > 0:
                q = i - 1
            else:
                q = 0
        for j in range(q, M):
            if P[j][0] == p:
                if P[j][1] == N:
                    ans = ("POSSIBLE")
                    break
            elif P[j][0] > p:
                if q >= 0:
                    q = j - 1
                else:
                    q = 0
                break
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
a_to = []
N_to = []
for i in range(M):
	a, b = map(int,input().split(" "))
	if a == 1 or b == 1:
		a_to.append(max(a,b))
	elif b == N or a == N:
		N_to.append(min(a,b))

a_set = set(a_to)
N_set = set(N_to)

if (len(a_set&N_set) >= 1):
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

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

ok1 = [False] * n
ok2 = [False] * n

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a == 0:
        ok1[b] = True
    if b == n - 1:
        ok2[a] = True

for m in range(n):
    if ok1[m] and ok2[m]:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
aa = [[]*n for i in range(n)]
ans = "IMPOSSIBLE"
for i in range(m):
  k = list(map(int, input().split()))
  aa[k[0]-1].append(k[1]-1)
  aa[k[1]-1].append(k[0]-1)
tmp = aa[0]
for j in range(len(tmp)):
  if n-1 in aa[tmp[j]]:
    ans = "POSSIBLE"
print(ans)

Submission status: Accepted

Solution code:
N, M =map(int,input().split())
F=[]
L=[]


for i in range(M):
    a, b=map(int,input().split())
    if a==1:
        F.append(b)

    if b==N:
        L.append(a)

FF=set(F)
LL=set(L)

for _ in FF:
    if _ in LL:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

island = [[]for i in range(n+1)]

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

flag = True

for i in island[1]:
    for k in island[i]:
        if k == n:
            print('POSSIBLE')
            flag = False
            break
    if flag is False:
        break

if flag is True:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:

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

edge_1toANY = [0 for n in range(N+1)]
edge_ANYtoN = [0 for n in range(N+1)]

for m in range(M):
    a,b = list(map(int,input().split()))
    if a == 1:
        edge_1toANY[b] = 1
    if b == N:
        edge_ANYtoN[a] = 1

flag = False
for n in range(N+1):
    if edge_1toANY[n] == 1:
        if edge_ANYtoN[n] == 1:
            flag = True
            break

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
from collections import deque


class EndLoop(Exception):
    pass


def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            Deque1 = deque()
            DequeN = deque()
            edges_1 = [False] * N
            edges_N = [False] * N
            Deque1.extend(edges_1)
            DequeN.extend(edges_N)

            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                if a == 1:
                    Deque1[b - 1] = True
                elif b == 1:
                    Deque1[a - 1] = True
                elif a == N:
                    DequeN[b - 1] = True
                elif b == N:
                    DequeN[a - 1] = True
                else:
                    pass

            for i in range(N):
                if Deque1[i] == True and DequeN[i] == True:
                    print("POSSIBLE")
                    raise EndLoop

            print("IMPOSSIBLE")
            break
        except:
            break


solve()

Submission status: Accepted

Solution code:
N, M = [int(n) for n in input().split()]
check = [0] * N
for m in range(M):
  a, b = [int(n) - 1 for n in input().split()]
  if a == 0:
    check[b] += 1
  if b == N-1:
    check[a] += 1
flag = False
for n in range(N):
  if check[n] == 2:
    flag = True

if flag == True:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# coding: utf-8
from sys import stdin
input = stdin.readline

N , M = map(int,input().split())
start_input = set()
goal_input = set()

for _ in range(M):
    x , y = map(int,input().split())
    if x == 1:
        start_input.add(y)
    elif y == N:
        goal_input.add(x)
    
if start_input & goal_input:
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

to_middle = set()           #  島1から渡ることのできる島
from_middle = set()         #  島Nへ渡ることのできる島
N, M = map(int, (input().split()))
for _ in range(M):
    f, t = map(int, (input().split()))
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
to_middle = set()           #  島1から渡ることのできる島
from_middle = set()         #  島Nへ渡ることのできる島
N, M = map(int, (input().split()))
for _ in range(M):
    f, t = map(int, (input().split()))
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
to_middle = set()           #  島1から渡ることのできる島
from_middle = set()         #  島Nへ渡ることのできる島
N, M = map(int, input().split())
for _ in range(M):
    f, t = map(int, input().split())
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc068.contest.atcoder.jp/tasks/arc079_a
AC
"""

def solve(routes, N):
    result = 'IMPOSSIBLE'
    to_middle = set()           #  島1から渡ることのできる島
    from_middle = set()         #  島Nへ渡ることのできる島
    for f, t in routes:
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        result = 'POSSIBLE'
    return result



def main():
    N, M = map(int, input().split())
    routes = []
    for _ in range(M):
        routes.append([int(x) for x in input().split()])
    result = solve(routes, N)
    print(result)


if __name__ == '__main__':
    # main()

    to_middle = set()           #  島1から渡ることのできる島
    from_middle = set()         #  島Nへ渡ることのできる島
    N, M = map(int, input().split())
    for _ in range(M):
        f, t = map(int, input().split())
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc068.contest.atcoder.jp/tasks/arc079_a

"""

def solve(routes, N):
    result = 'IMPOSSIBLE'
    to_middle = set()           #  島1から渡ることのできる島
    from_middle = set()         #  島Nへ渡ることのできる島
    for f, t in routes:
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        result = 'POSSIBLE'
    return result



def main():
    N, M = map(int, input().split())
    routes = []
    for _ in range(M):
        routes.append([int(x) for x in input().split()])
    result = solve(routes, N)
    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product, groupby
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for a in graph[1]:
        if N in graph.get(a, []):
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

d = defaultdict(list)
goal, n = map(int, input().split())
for _ in range(n):
  f, t = map(int, input().split())
  d[f].append(t)
  d[t].append(f)
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

a = [0] * n

for i in range(m):
    if ab[i][0] == 1:
        a[ab[i][1]] += 1
    if ab[i][1] == n:
        a[ab[i][0]] += 1

if max(a) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
cnt=0
s=[]
kkk=[]
lll=[]
mmm=[]
nnn=[]
while cnt<m:
    num=list(map(int,input().split()))
    s+=num
    cnt+=1
for x in range(m*2):
    if s[x]==n:
        if x%2==0:
            kkk+=[x+1]
        else:
            kkk+=[x-1]
for x in range(len(kkk)):
        lll+=[s[kkk[x]]]
for x in range(m*2):
    if s[x]==1:
        if x%2==0:
            mmm+=[x+1]
        else:
            mmm+=[x-1]
for x in range(len(mmm)):
        nnn+=[s[mmm[x]]]
if len(list(set(lll)&set(nnn)))>0:
    ans="POSSIBLE"
else:
    ans="IMPOSSIBLE"
print(ans)

Submission status: Accepted

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

nxt = set()
prv = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        nxt.add(b)
    elif b == N:
        prv.add(a)

if nxt & prv:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        set_a.add(b)
    if b == N:
        set_b.add(a)

if set_a & set_b:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
lines = sys.stdin.readlines()
N,M = map(int,(lines[0].split()))
seta,setb = set(),set()
for m in range(1,M+1):
    a,b = map(int,(lines[m].split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import fileinput

input = fileinput.input().readline

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

seta,setb = set(),set()

for m in range(M):
    a,b = map(int,(input().split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)
        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

ans = "IMPOSSIBLE"

seta,setb = set(),set()

for m in range(M):
    a,b = map(int,(input().split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)
        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

ans = "IMPOSSIBLE"

seta,setb = set(),set()
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        seta.add(b-1)
    if b-1 == N-1:
        bf[m] = True
        setb.add(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in seta:
    if ans == "POSSIBLE":
        break
    if a in setb:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

    flag = 1
    for i in d[1]:
        if n in d[i]:
            print("POSSIBLE")
            flag = 0
            break

    if flag: print("IMPOSSIBLE")
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

N, M = map(int, raw_input().split())
dic = {}

for i in range(M):
    tmp = map(int, raw_input().split())
    if tmp[0] not in dic:
        dic[tmp[0]] = []
        dic[tmp[0]].append(tmp[1])
    else:
        dic[tmp[0]].append(tmp[1])
    if tmp[1] not in dic:
        dic[tmp[1]] = []
        dic[tmp[1]].append(tmp[0])
    else:
        dic[tmp[1]].append(tmp[0])

flag = 0

key1 = copy.deepcopy(dic[1])
for i in key1:
    key2 = copy.deepcopy(dic[i])
    for i in key2:
        if i == N:
            flag = 1

if flag == 1:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Submission status: Accepted

Solution code:
def main():
    # 1 to N => 1 to X to N
    N, M = map(int, input().split())
    from1 = set()
    toN = set()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from1.add(b)
        if b == N:
            toN.add(a)

    if from1 & toN:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dfs(i, p):
    if(p == n):
        return 1
    if(i == 2):
        return 0
    ret = 0
    for q in adj[p]:
        ret += dfs(i+1, q)
    return ret

n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
ans = dfs(0, 1)

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

Submission status: Accepted

Solution code:
a=[]
b={}
n,m = map(int,input().split())
for _ in range(m):
	i,j = map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Accepted

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

n, m = map(int, raw_input().split())
island = [[] for i in range(n+1)]
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, raw_input().split())
    island[a].append(b)
    island[b].append(a)
for i in island[1]:
    if(n in island[i]):
        ans = 'POSSIBLE'
        break
print(ans)