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: Wrong Answer

Solution code:
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
gcnt=0
gvisited=[False]*n
def dfs(u,cnt,visited):
  global gcnt
  global gvisited
  visited=visited[:]
  cnt=cnt
  visited[u]=True
  # print(cnt)
  if visited[-1]==True:
    # print('反応した',cnt,visited)
    gcnt=cnt
    gvisited=visited
    return gcnt,gvisited
  for v in edges[u]:
    if visited[v]==False:
      cnt+=1
      dfs(v,cnt,visited)
  return gcnt,gvisited

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

cnt,visited=dfs(0,cnt,visited)
# print(cnt,visited)
if visited[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
goal,n=map(int,input().split())
A=[]
for i in range(n):
  A.append(list(map(int,input().split())))
dp=[0 for i in range(200010)]
for i in range(n):
  if 1 in A[i]:
    dp[A[i][1]+1]+=1
if dp[goal+1]==1:
  print("POSSIBLE")
  exit()

tp=[0 for i in range(200010)]
for i in range(n):
  if goal in A[i]:
    dp[A[i][1-A[i].index(goal)]+1]+=1
for i in range(200010):
  if dp[i]==tp[i]==1:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

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

mylist=[]
for i in range(m):
    mylist.append(input().split())

#print(mylist)
mydict=dict(mylist)
myvalue=mydict.get('1')
if mydict.get(myvalue)==str(n):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

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]:
    check1[i] = 1

check2 = [0] * N

for i in check1:
    for j in matrix[i]:
        check2[j] = 1

if check2[N-1] == 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

check = [0] * N
check[0] = 1

deque = [0]

while deque:
    now = deque.pop()
    for i in matrix[now]:
        if check[i] == 0:
            deque.append(i)
            check[i] = 1
if check[N-1] == 1:
    print('POSSIBLE')
else:
    print(('IMPOSSIBLE'))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = [0 for _ in range(N+1)]
stack = [[N,0]]
count[N] = 1
ok = False
for i in range(2*M):
    if stack == []:
        break
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                if count[i] == 0:
                    stack.append([i,arr[1]+1])
                    count[i] = 1
print('IMPOSSIBLE' if ok else 'POSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = 0
stack = [[N,0]]
ok = False
while(stack != []):
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                stack.append([i,arr[1]+1])
print('IMPOSSIBLE' if ok else 'POSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = 0
stack = [N]
ok = False
while(count<2):
    if stack == []:
        break
    go = stack.pop(-1)
    for i in edge[go]:
        stack.append(i)
        if i == 1:
            ok = True
    count += 1
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Submission status: Wrong Answer

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())
    a -= 1
    b -= 1
    matrix[a].append(b)
    matrix[b].append(a)
for i in matrix[0]:
    for j in matrix[n-1]:
        if i == j:
            print('possible')
            exit()
print('impossible')

Submission status: Wrong Answer

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

tmp = []
check = []
for i in range(M):
  a, b = A[i][0], A[i][1]
  if(a == 1):
    tmp.append((a, b))
  if(b == N):
    check.append((a, b))

if(check == []):
  print("IMPOSSIBLE")
else:
  for c in check:
    for t in tmp:
      if(t[1] in c):
        print("POSSIBLE")
        break
  else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

tmp = []
check = []
for i in range(M):
  a, b = A[i][0], A[i][1]
  if(a == 1):
    tmp.append((a, b))
  if(b == N):
    check.append((a, b))

if(check == []):
  print("IMPOSSIBLE")
else:
  for c in check:
    for t in tmp:
      if(t[1] in c):
        print("POSSIBLE")
        break
    else:
      print("IMPOSSIBLE")

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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-1:
        if path[b-1][0]:
            flag=True
            break
        path[b-1][1]=True
    if a==0:
        if path[b-1][1]:
            flag=True
            break
        path[b-1][0]=True
    if b==N-1:
        if path[a-1][0]:
            flag=True
            break
        path[a-1][1]=True
    if b==0:
        if path[a-1][1]:
            flag=True
            break
        path[a-1][0]=True

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

Submission status: Wrong Answer

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 is 1:
        to_one[b] = True
    if b is 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: Wrong Answer

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(" "))
    a, b = a - 1, b - 1
    if a is 0:
        to_one[b] = True
    if b is N - 1:
        to_N[a] = True

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

if not res:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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 is 1:
        to_one[b - 1] = True
    if b is N:
        to_N[a - 1] = True

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

if not res:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

edge = []

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

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

if not res:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

edge = []

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

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

if not res:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

edge = []

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

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


if not res:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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: Wrong Answer

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)
    min_len=0
    while max_len>min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif abs(min_len-max_len)==1 and li[mid]!=a:
            break
        elif li[mid]<a:
            min_len=mid
        else:
            max_len=mid
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: Wrong Answer

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

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

# may be faster filter (1, *) and (*, N) before sorting ?

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") # oh...

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break


###
#for i in range(len(one)):
#    for j in range(len(two)):
#        if one[i] == two[j]:
#            flag = 1
#            print("POSSIBLE")
#            break
#    if flag == 1:
#        break
###
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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: Wrong Answer

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

st = []
tt = []

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

st.sort()
tt.sort()
result = 'IMPOSSIBLE'

j = 0
for s in st:
    for i in range(j, len(tt)):
        if s < tt[i]:
            pass
        else:
            if s == tt[i]:
                result = 'POSSIBLE'
                break
            else:
                j = i
                break


    if result == 'POSSIBLE':
        break


print(result)

Submission status: Wrong Answer

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 M == L[i][0]:
        g.append(L[i][1])
    if M == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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 M == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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+1]:
        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: Wrong Answer

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)
        
print(starts, ends)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

if set(mid) & set(las) != 0:
    ans =1

print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

if set(mid) & set(las) != 0:
    ans =1

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

if set(mid) & set(las):
    ans = 1

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

for i in mid:
    if i in las:
        ans = 1
        break

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
ans = 0
tyukan = []
saigo = []

for i in range(M):
    if ab[i][0] == 1:
        tyukan.append(ab[i][1])

for i in range(M):
    if ab[i][0] in tyukan:
        if ab[i][1] == N:
            ans =1
            break

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a, b = [0]*M, [0]*M
ans = 0
tyukan = []
saigo = []
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        tyukan.append(b[i])
    
    elif b[i] == N:
        saigo.append(a[i])
    
for i in tyukan:
    if i in saigo:
        ans = 1
        break

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a, b = [0]*M, [0]*M
ans = 0
tyukan = []
saigo = []
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        tyukan.append(b[i])
    
    elif b[i] == N:
        saigo.append(a[i])
    
for i in saigo:
    if i in tyukan:
        ans = 1
        break

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Wrong Answer

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
second = 0

for l in line:
    if l[0] == start:
        second = l[1]
    if l[1] == start:
        second = l[0]

for l in line:
    if l[0] == second:
        if l[1] == end:
            print('POSSIBLE')
            exit()
    if l[1] == second:
        if l[0] == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
second = 0

for l in line:
    if l[0] == start:
        second = l[1]

for l in line:
    if l[0] == second:
        if l[1] == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
second = 0

for l in line:
    if l[0] == start:
        second = l[1]

for l in line:
    if l[0] == second:
        endp = l[1]
        if endp == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
second = 0

for l in line:
    if l[0] == start:
        second = l[1]
        if second == end:
            print('POSSIBLE')
            exit()
if second == 0:
    print('IMPOSSIBLE')
    exit()

for l in line:
    if l[0] == second:
        endp = l[1]
        if endp == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

    islands_to_1 = []
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1.append(max(boat))

        if n in boat:
            islands_to_n.append(min(boat))

    print(islands_to_n)
    print(islands_to_1)

    for island_to_1 in islands_to_1:
        if island_to_1 in islands_to_n:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

s=[]
g=[]
for i, j in ab:
    if i==1:
        s.append(j)
    elif j==1:
        s.append(i)
    elif i==N:
        g.append(j)
    elif j==N:
        g.append(i)
flag=0
for i in range(len(s)):
    for j in range(len(g)):
        if s[i]==g[j]:
            flag=1

print("POSSIBLE"  if flag else "INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X[E-1] = 1
    if E == N:
        Y[S-1] = 1
for i in range(N):
    if X[i] == Y[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
s1 = raw_input().split(' ')
n, m = int(s1[0]), int(s1[1])
i2il = {}
for _ in range(m):
    s = raw_input().split(' ')
    if s[0] in i2il:
        i2il[s[0]].append(s[1])
    else:
        i2il[s[0]] = [s[1]]
    if s[1] in i2il:
        i2il[s[1]].append(s[0])
    else:
        i2il[s[1]] = [s[0]]
if '1' not in i2il or s1[1] not in i2il:
    print 'IMPOSSIBLE'
else:
    mid = i2il['1']
    bhit = False
    for m in mid:
        if s1[0] in i2il[m]:
            print 'POSSIBLE'
            bhit = True
            break
    if not bhit:
        print 'IMPOSSIBLE'

Submission status: Wrong Answer

Solution code:
s1 = raw_input().split(' ')
n, m = int(s1[0]), int(s1[1])
i2il = {}
for _ in range(m):
    s = raw_input().split(' ')
    if s[0] in i2il:
        i2il[s[0]].append(s[1])
    else:
        i2il[s[0]] = [s[1]]
    if s[1] in i2il:
        i2il[s[1]].append(s[0])
    else:
        i2il[s[1]] = [s[0]]
if '1' not in i2il or s1[1] not in i2il:
    print 'IMPOSSIBLE'
else:
    mid = i2il['1']
    bhit = False
    for m in mid:
        if s1[1] in i2il[m]:
            print 'POSSIBLE'
            bhit = True
            break
    if not bhit:
        print 'IMPOSSIBLE'

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
    # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.parent = [i for i in range(n + 1)]
    # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)
    #検索
    def find(self, x):
    #根ならその番号を返す
        if self.parent[x] == x:
            return x
        else:
    # 走査していく過程で親を書き換える
            self.parent[x] = self.find(self.parent[x])
            return self.find(self.parent[x])
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    #併合
    def unite(self, x, y):
    #根を探す
        x = self.find(x)
        y = self.find(y)
    # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
    # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

    u = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        u.unite(a, b)
    if u.same_check(1, n):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[1] == n:
		from_one.add(ab_i[0])
	
print("POSSIBLE" if from_one | to_n else "IMPOSSIBLE")

Submission status: Wrong Answer

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

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[0] == n:
		from_one.add(ab_i[1])
	
print("POSSIBLE" if from_one | to_n else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = set()
for i in a:
    if i[0]==1 or i[1]==N:
        b.add((i[0],i[1]))
print(b)
for i in range(2,N):
    if (1,i) in b and (i,N) in b:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = []
for i in a:
    if i[0]==1 or i[1]==N:
        b.append(i)
print(b)
for i in range(2,N):
    if [1,i] in b and [i,N] in b:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(" "))
first = []
second = []
flag = 0

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append(b)
  if a == 1:
    first.append(a)
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  for j in range(len(first)):
    for k in range(len(second)):
      if first[j] == second[k]:
        print("POSSIBLE")
        flag = 1
        break
  if flag == 0:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

iki=[]
kae=[]

c=0
flag=-1

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

l=len(iki)
iki2=set(iki)
l2=len(iki2)

#print(iki)
                
if l>l2:
    print("POSSIBLE")
else:
    print("INPOSSIBLE")

Submission status: Wrong Answer

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

siCheck = [0 for i in range(N)]
inCheck = [0 for i in range(N)]

for i in range(M):
    if a[i][0] == '1':
        siCheck[int(a[i][1])-1] = True
    else:
        siCheck[int(a[i][1])-1] = False
    if int(a[i][1]) == N:
        inCheck[int(a[i][0])-1] = True
    else:
        inCheck[int(a[i][0])-1] = False

for i in range(N):
    if siCheck[i] and inCheck[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M =[int(i) for i in input().split(' ')]
table = [0]*N

for i in range(M):
    a,b = [int(i) for i in input().split(' ')]
    if a==1:
        table[b-1] +=1
        if b==M:
            table[b-1] +=1
    if b==N:
        table[a-1]+=1
#    print(table)
flag = True
for i in table:
    if i==2:
        print("POSSIBLE")
        flag = False
        break

if flag:
    print("IMPOSSIBLE")

#print(table)

Submission status: Wrong Answer

Solution code:
import math

# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for _ in range(M)]

edge_lst = sorted(edge_lst)

d_1 = [] # 頂点1から距離1の頂点

i = 0

while i < M and edge_lst[i][0] == 1:
    d_1.append(edge_lst[i][1])
    i += 1

edge_lst = sorted(edge_lst, reverse = True)

d_N = [] # 頂点Nから距離1の頂点

j = 0

while j < M and edge_lst[j][1] == N:
    d_N.append(edge_lst[j][0])
    j += 1

for n in d_1:
    if n in d_N:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
    
aaa = 0
tbin_1 = []
tbin_n = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        tbin_1.append(xxx[1])
    elif xxx[1] == n :
        tbin_n.append(xxx[0])
        
    if xxx[1] in tbin_n:
        aaa = 1
        break
    if xxx[0] in tbin_1:
        aaa = 1
        break
    else:
        None


if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int,input().split(" "))
a = []
b = []
judge = True
for i in range(M):
    tempa,tempb = map(int,input().split(" "))
    a.append(tempa)
    b.append(tempb)
a = np.array(a)
b = np.array(b)
temp_a = a[np.where(b == N)]
if len(temp_a) == 0:
    print("IMPOSSIBLE")
else:
    # temp_b = []
    for i in range(len(temp_a)):
        if len(np.where(b == temp_a[i])) != 0: 
            temp_b = np.where(b == temp_a[i])[0]
            for i in temp_b:
                if a[i] == 1:
                    print("POSSIBLE")
                    judge = False
            if judge:
                print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  if(x==n-1 and dist[x]==2):
    print("POSSIBLE")
    sys.exit()
  elif(x==n-1 and dist[x]!=INF):
    print("INPOSSIBLE")
    sys.exit()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  if(dist[x]>2):
    print("IMPOSSIBLE")
    sys.exit()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Wrong Answer

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

D = {}
for m in range(M):
    a, b = [int(n) for n in input().split()]
    if a in D.keys():
        D[a].append(b)
    else:
        D[a] = [b]
possible = False
for n in D[1]:
    if N in D.get(n, []):
        possible = True

print('POSSIBLE' if possible else 'INPOSSIBLE')