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())
d = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
if 1 not in d:
    print('IMPOSSIBLE')
else:
    for i in d[1]:
        if i in d:
            if N in d[i]:
                print('POSSIBLE')
                break
    else:
        print('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:
        B.add(b)
    if b == n:
        A.add(a)
        
if len(A&B) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(m):
    s, g = map(int, input().split())
    if s == 1:
        G.add(g)
    if g == n:
        S.add(s)

if len(S&G) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
onelist,nlist = [],[]
for i in range(M):
    aa,bb = map(int,input().split())
    if aa == 1:
        onelist.append(bb)
    if bb == N:
        nlist.append(aa)


if len(set(onelist) & set(nlist)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
#068-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,m=IL()
nl=[[] for i in range(n)]
for i in range(m):
    a,b=IL()
    nl[a-1].append(b-1)
for i in nl[0]:
    if n-1 in nl[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [False]*(N+1)
for _ in range(M):
    res = None
    a, b = map(int, input().split())
    if a == 1:
        res = b
    if b == N:
        res = a
    if res is not None:
        if p[res]:
            print('POSSIBLE')
            exit()
        else:
            p[res] = True
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
fir = []
sec = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fir.append(b)
    elif a == n:
        sec.append(b)
    if b == 1:
        fir.append(a)
    elif b == n:
        sec.append(a)
fir.sort()
sec.sort()
flag = True
for i in fir:
    j = 0
    while flag and sec:
        if i > sec[j]:
            del sec[j]
        elif i == sec[j]:
            print("POSSIBLE")
            flag = False
        else:
            break
if flag == True:
    print("IMPOSSIBLE")

Submission status: Accepted

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

print("POSSIBLE" if A[0] & A[N-1] != set() else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
if m == 1:
    input()
    print('IMPOSSIBLE')
    sys.exit()
mid = [];move = [None]*m
for i in range(m):
    a,b = map(int,input().split())
    move[i] = [a,b]
    if a == 1:mid.append(b)
    if b == 1:mid.append(a)
    if a == n:mid.append(b)
    if b == n:mid.append(a)
check = False
if len(mid) != len(set(mid)):check = True
if check == True:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Accepted

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

mylist = [[int(i) for i in input().split()] for i in range(m)] 
#print(mylist)

mylist1=[mylist[i][1] for i in range(m) if mylist[i][0]==1]
#print(mylist1)

mylist2=[mylist[i][0] for i in range(m) if mylist[i][1]==n]
#print(mylist2)


if len(set(mylist1) & set(mylist2)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

a=[]
b=[]
l1=[False for i in range(n)]
ln=[False for i in range(n)]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if c[0]==1 or c[1]==1:
        l1[c[0]*c[1]]=True
    if c[0]==n or c[1]==n:
        ln[c[0]*c[1]//n]=True

for i in range(n):
    if l1[i] and ln[i]:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
matrix = [[] for i in range(N)]
check1 = [0] * N
check1[0] = 1

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
routes = [[] for i in range(n+1)]
flag = False
for i in range(m):
  a, b = map(int, input().split())
  routes[a].append(b)
  routes[b].append(a)

for i in routes[1]:
  if n in routes[i]:
    flag = True

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(list(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Submission status: Accepted

Solution code:
def abc068_c():
    from collections import Counter
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    candidates = []

    for i in range(m):
        if ab[i][0] == 1:
            candidates.append(ab[i][1])
        elif ab[i][1] == n:
            candidates.append(ab[i][0])

    if max(Counter(candidates).values()) >= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


abc068_c()

Submission status: Accepted

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

ab = []
for _ in range(M):
  ab.append(tuple(map(int, input().strip().split())))

from1 = set()
is_reach = False
for a, b in sorted(ab, key=lambda x: x[0]):
  if a == 1:
    from1.add(b)
  else:
    if a in from1 and b == N:
      is_reach = True
      break
if is_reach:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

tmp = [0]*N
check = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    tmp[b] += 1
  elif(b == N):
    check[a] += 1

for i in range(len(tmp)):
  if(check[i] == 1 and tmp[i] == 1):
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

"""
tmp = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    tmp[b] += 1
  elif(b == N):
    tmp[a] += 1

if(2 in tmp):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
"""

Submission status: Accepted

Solution code:
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)

for e1 in g[1]:
    for e2 in g[e1]:
        if e2 == N:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ss = [set(), set()]
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        if a == 0:
            ss[0].add(b)
        elif a == n - 1:
            ss[1].add(b)
        if b == 0:
            ss[0].add(a)
        elif b == n - 1:
            ss[1].add(a)
    if ss[0] & ss[1]:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
L=[];l=[]
for k in range(n):
  L.append(0)
for i in range(m):
  x=list(map(int,input().split()))
  l.append(x)
  if x[0]==1:
    L[x[1]]+=1
  if x[1]==1:
    L[x[0]]+=1
  if x[0]==n:
    L[x[1]]+=1
  if x[1]==n:
    L[x[0]]+=1
if max(L)==2:print('POSSIBLE')
else: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)
    elif b==1:
        Start.append(a)
    if a==N:
        Goal.append(b)
    elif b==N:
        Goal.append(a)
    
S=set(Start)
G=set(Goal)
if len(S&G)>0:
    print("POSSIBLE")
elif len(S&G)==0:
    print("IMPOSSIBLE")

Submission status: Accepted

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

a = [tuple(map(int, input().split())) for _ in range(m)]

p = []
q = []

for i in range(m):
    if a[i][0] == 1:
        p.append(a[i][1])
    elif a[i][1] == n:
        q.append(a[i][0])

if len(set(p)&set(q)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
x=list(map(int,input().split()))
flg=0
a=[[] for i in range(x[0])]
for i in range(x[1]):
    y=list(map(int,input().split()))
    a[y[0]].append(y[1])
for i in range(1,x[0]):
    a[i].sort(reverse=True)
for i in range(len(a[1])):
    if len(a[a[1][i]]) > 0 and a[a[1][i]][0]==x[0]:
        flg=1
        break
if flg==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
path = [[False,False] for i in range(N)]
flag=False
for i in range(M):
    a,b = list(map(int,input().split()))
    if a==N:
        if path[b-1][0]:
            flag=True
            
        path[b-1][1]=True
    if a==1:
        if path[b-1][1]:
            flag=True
            
        path[b-1][0]=True
    if b==N:
        if path[a-1][0]:
            flag=True
            
        path[a-1][1]=True
    if b==1:
        if path[a-1][1]:
            flag=True
            
        path[a-1][0]=True

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

Submission status: Accepted

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

to_one = [False] * N
to_N = [False] * N
for m in range(M):
    a, b = map(int, input().strip().split(" "))
    if a == 1:
        to_one[b] = True
    if b == N:
        to_N[a] = True

res = False
for n in range(2, N):
    if to_N[n] and to_one[n]:
        print("POSSIBLE")
        res = True
        break

if not res:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from sys import stderr, setrecursionlimit
from functools import reduce
from operator import add
from collections import defaultdict as dd
setrecursionlimit(2147483647)
def f(): return [int(i) for i in input().split()]
def yes(n): print("Yes" if n else "No")
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(str(item))
        stderr.write(sep)
    stderr.write(end)

n, m = f()
graph = dd(list)
for i in range(m):
    a, b = f()
    graph[a].append(b)

for a in graph[1]:
    if n not in graph[a]:
        continue
    print("POSSIBLE")
    break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]
to_halfway = [0]*(N+1)
from_halfway = [0]*(N+1)
for a, b in AB:
    if a == 1:
        to_halfway[b] = 1
    elif b == N:
        from_halfway[a] = 1
for i in range(N+1):
    if to_halfway[i]*from_halfway[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
a = [0 for i in range(m)]
b = [0 for i in range(m)]
semiGoal = [0 for i in range(n)]
for i in range(m):
    a[i], b[i] = [int(i) - 1 for i in input().split()]
    if b[i] == n-1:
        semiGoal[a[i]] = 1
for i in range(m):
    if a[i] == 0 and semiGoal[b[i]] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = []
for i in range(m):#h:高さ
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
root = []
for i in range(n):
    root.append([])
for i in range(m):
    root[c[i][0] - 1].append(c[i][1])
root1 = root[0]
for v in root1:
    if n in root[v - 1]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
l_s,l_l,B_s,B_l = [],[],[],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        if b < N:
            B_s.append(b) #Nより小さい
        elif b > N:
            B_l.append(b) #Nより大きい
    if a == N:
        l_l.append(b) #Nより大きい
    elif b == N:
        l_s.append(a) #Nより小さい
common_1 = len(list(set(l_s) & set(B_s)))
common_2 = len(list(set(l_l) & set(B_l)))
if common_1 > 0 or common_2 > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


N, M = map(int, input().split())
lines = []
for _ in range(M):
    a, b = map(int, input().split())
    lines.append(Line(a, b))
second_islands = []
m = {}
for line in lines:
    m.setdefault(line.a, {})
    m[line.a][line.b] = 1
for line in lines:
    if line.a == 1:
        second_islands.append(line.b)

can_reach = False
for island in second_islands:
    if island in m:
        if N in m[island]:
            can_reach = True
            break
if (can_reach):
    print("POSSIBLE")
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)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)-1
    min_len=0
    while max_len>=min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif li[mid]<a:
            min_len=mid+1
        else:
            max_len=mid-1
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort()
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab_tmp = [list(map(int, input().split())) for i in range(M)]

ab = []
for ai, bi in ab_tmp:
    if ai == 1 or bi == N: ab.append([ai, bi])

ab.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1] if x[0] == 1 else x[0]) # oh...?

view = 0
for ai, bi in ab:
    if ai < 2: # search for new available 2nd dept.
        view = bi
        continue
    elif ai > view: continue # ignore unavailable 2nd dept.
    elif bi == N: # successful
        print("POSSIBLE")
        break
    else: continue # still evaluating
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
a,b = map(int,input().split(" "))
ar = [[] for j in range(a+1)]
for i in range(b):
    l = list(map(int,input().split(" ")))
    ar[l[0]].append(l[1])
    ar[l[1]].append(l[0])
count = 0
for r in ar[1]:
    for s in ar[r]:
        if s == a:
            count += 1
if count == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

s = [0 for _ in range(n)]
t = [0 for _ in range(n)]

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

    if a == 1:
        s[b-1] = 1
    if b == n:
        t[a-1] = 1

for i in range(n):
    if s[i] * t[i] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

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

P = []
for i in range(2) :
    for j in range(M) :
        if (L[j][i] == 1) or (L[j][i] == N) :
            if i == 0 :
                P.append(L[j][1])
            else :
                P.append(L[j][0])

Q = list(set(P))
if len(P) != len(Q) :
    flag = 1

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

Submission status: Accepted

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

t = [0] * N

for i in range(M):
    tmp = list(map(int, input().rstrip().split()))
    if tmp[0] == 1:
        t[tmp[1] - 1] |= 1
    
    if tmp[1] == N:
        t[tmp[0] - 1] |= 2


result = 'POSSIBLE' if 3 in t else 'IMPOSSIBLE'
print(result)

Submission status: Accepted

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

st = []
dic = {}

for i in range(M):
    s, t = list(map(int, input().rstrip().split()))
    if s == 1:
        st.append(t)
    
    if t == N:
        dic[s] = 0

result = 'IMPOSSIBLE'
for s in st:
    if s in dic:
        result = 'POSSIBLE'
        break


print(result)

Submission status: Accepted

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

ab = []
bn = {}
for i in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] == 1:
        ab.append(tmp[1])
    elif tmp[1] == n:
        bn[tmp[0]] = 1
for i in ab:
    if i == n:
        print('POSSIBLE')
        sys.exit(0)
    elif i in bn:
        print('POSSIBLE')
        sys.exit(0)

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
c = [0]*(N+1)
for i in range(1,M+1):
  a, b = map(int, raw_input().split())
  if a in [1, N]:
    c[b] += 1
  if b in [1, N]:
    c[a] += 1
r = 'IMPOSSIBLE'
for j in range(1,N+1):
  if c[j]==2:
    r = 'POSSIBLE'
print r

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b, d = [0]*M, [0]*M, [0]*M
hoge, piyo = set(), set()
for i in range(M):
    ai, bi = map(int, input().split())
    if ai == 1 and bi == N:
        print('POSSIBLE')
        exit()
    elif ai == 1:
        hoge.add(bi)
    elif bi == N:
        piyo.add(ai)
if len(hoge.intersection(piyo)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def 解():
    iN,iM = [int(_) for _ in input().split()]
    a1 = [0]*iN
    aN = [0]*iN
    for i in range(iM):
        a,b = [int(_) for _ in input().split()]
        if a == 1:
            a1[b] = 1
        if b == iN:
            aN[a] = 1
    for i in range(iN):
        if a1[i] and aN[i]:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()

Submission status: Accepted

Solution code:
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    a1 = [0]*iN
    aN = [0]*iN
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    for a,b in aAB:
        if a == 1:
            a1[b] = 1
        if b == iN:
            aN[a] = 1
    for i in range(iN):
        if a1[i] and aN[i]:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()

Submission status: Accepted

Solution code:
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split() ] for sLine in sys.stdin.readlines()]
    d1 = set()
    dN = set()
    for a,b in aAB:
        if a == 1 :
            d1.add(b)
        if b == iN:
            dN.add(a)
    if d1 & dN == set():
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
解()

Submission status: Accepted

Solution code:
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    dT = {}
    def addTree(dT,a,b):
        if a in dT:
            dT[a].add(b)
        else:
            dT[a] = {b}
    for a,b in aAB:
        addTree(dT,a,b)
        addTree(dT,b,a)
    if  1 not in dT or iN  not in dT:
        print("IMPOSSIBLE")
    elif 0 < len(dT[1] & dT[iN]) :
        print("POSSIBLE")
    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)]
s = []
g = []
for i in range(M):
    if 1 == L[i][0]:
        s.append(L[i][1])
    if 1 == L[i][1]:
        s.append(L[i][0])
        
for i in range(M):
    if N == L[i][0]:
        g.append(L[i][1])
    if N == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

t_a = []
t_b = []

ans = 'IMPOSSIBLE'
for i in range(M):
	if l[i][0] == 1:
		t_a.append(l[i][1])
	elif l[i][1] == N:
		t_b.append(l[i][0])
t_and = set(t_a) & set(t_b)
t_and_l = list(t_and)
if len(t_and_l) > 0:
	ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

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

F = [0 for _ in range(N)]   # from
T = [0 for _ in range(N)]   # to

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        F[b-1] = 1
    if b == N:
        T[a-1] = 1

for i in range(1, N):
    if F[i] == T[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
for _ in range(m):
  j,k=map(int,input().split())
  l[j].append(k)
for i in l[1][1:]:
  if n in l[i]:break
  if i==l[1][-1]:print('IM',end='')
print('POSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
graph0 = [0 for _ in range(N)]
graphN = [0 for _ in range(N)]

for _ in range(M):
    ab = list(map(int, input().split()))
    a,b = ab[0],ab[1]
    if a == 1:
        graph0[b-1] = 1
    if b == N:
        graphN[a-1] = 1

for i in range(1,N):
    if graph0[i] == 1 and graphN[i] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

if len(s & t) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if p < len(t_n)-1 and f_1[i] == t_n[p]:
        jedge = 1
        break
    elif p == len(t_n)-1 and f_1[i] == t_n[p]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
SetFrom, SetTo = set(), set()
for i in range(M):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    if a == 1:
        SetFrom |= {b}
    elif b == N:
        SetTo |= {a}
print("POSSIBLE" if SetFrom & SetTo else "IMPOSSIBLE")

Submission status: Accepted

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

print("POSSIBLE" if set(S[0]) & set(S[N-1]) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import bisect

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

AB = sorted(AB)

first = []
for a,b in AB:
    if a == 1:
        first.append(b)
    else:
        break

AB = sorted(AB, key=lambda x:x[1], reverse=True)
sec = []
for a,b in AB:
    if b == N:
        sec.append(a)
    else:
        break

if len(sec) >= 100:
    for f in first:
        ind = bisect.bisect_left(sec, f, 0, len(sec))
        if sec[ind] == f:
            print('POSSIBLE')
            exit()
else:
    for f in first:
        if f in sec:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
starts = set([])
ends = set([])

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

ans = "POSSIBLE" if len(starts&ends)>=1 else "IMPOSSIBLE"
print(ans)

Submission status: Accepted

Solution code:
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

s = []

for i in range(m):
	s.append(list(map(int,input().split())))

a1 = []
an = []
for i in range(m):
	if s[i][0]==1:
		a1.append(s[i][1])

for i in range(m):
	if s[i][1]==n:
		an.append(s[i][0])

if len(list(set(a1)&set(an)))>0:
	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 == 1:
        s.add(b)
    elif b == N:
        t.add(a)

if len(s & t) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
list_ab = []
for i in range(m):
    list_ab.append(list(map(int, input().split())))
list1 = []
listn = []
for i in range(m):
    if list_ab[i][0] == 1:
        list1.append(list_ab[i][1])
for i in range(m):
    if list_ab[i][1] == n:
        listn.append(list_ab[i][0])

listn.sort()
def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"
ans = "IMPOSSIBLE"
for i in range(len(list1)):
    if binarySearch(listn, list1[i]) != "NOT_FOUND":
        ans = "POSSIBLE"
        break

print(ans)

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)

flag = [0 for i in range(n)]

def bfs(s):
    d = 0
    flag[s] = 1
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            if v[1] < 1:
                q.append((i, d+1))
            if v[1] == 1 and i == n-1:
                return True
    return False

print("POSSIBLE" if bfs(0) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

from1 = set()
toN = set()

for _ in range(m):
    a,b = li()
    if a==1:
        from1.add(b)
    elif b==1:
        from1.add(a)
        
    elif a==n:
        toN.add(b)
    elif b==n:
        toN.add(a)

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