Problem:


Score : 300 points

Problem Statement

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

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

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

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

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

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

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

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

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

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

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

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

Sample Output 4

POSSIBLE

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



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    p = [False] * n
    q = p[:]
    for i in range(m):
        j, k = map(int, input().split())
        if j == 1:
            p[k] = True
        if j == n:
            q[k] = True
        elif k == n:
            q[j] = True
    for i in range(n):
        if p[i] and q[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1 or a == n:
            d[a] += [b]
        if b == 1 or b == n:
            d[b] += [a]
    if 1 in d and n in d:
        dd = collections.defaultdict(list)
        for v in d[n]:
            dd[v]
        for i in d[1]:
            if i in dd:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE ")


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    one = {}
    enu = {}
    
    for i in range(M):
        a,b = map(int,input().split())
        if a==1:
            one[b] = 1
        elif b==1:
            one[a] = 1
        elif a==N:
            enu[b] = 1
        elif b==N:
            enu[a] = 1
    flag = 0
    for i in one:
        if i in enu:
            flag = 1
            break
    if flag==1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    
    
main()

Submission status: Accepted

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

bridge1 = []
bridge1_right = set()
bridge2 = []
bridge2_left = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
        bridge1_right.add(b)
    if b == N:
        bridge2.append((a, b))
        bridge2_left.add(a)

if len(bridge1) == 0 or len(bridge2) == 0:
    print('IMPOSSIBLE')
    exit()

if len(bridge1_right & bridge2_left) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ad = collections.defaultdict(list)
    bd = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1:
            ad[b] = 1
        if b == 1:
            ad[a] = 1

        if a == n:
            bd[b] = 1
        if b == n:
            bd[a] = 1
    for k, v in ad.items():
        if k in bd:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
C1 = [0]*(N+1)
C2 = [0]*(N+1)

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        C1[b] +=1
    if b == N:
        C2[a] +=1

for i in range(1,N+1):
    if C1[i]==1 and C2[i]==1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
S = [False for _ in range(N)]
G = [False for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    if a == 0 and b == N - 1:
        print("POSSIBLE")
        exit()
    if a == 0:
        if G[b]:
            print("POSSIBLE")
            exit()
        S[b] = True
    if b == N - 1:
        if S[a]:
            print("POSSIBLE")
            exit()
        G[a] = True

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split()))for i in[0]*b]
d=[]
e=[]
for i in c:
  if i[0]==1:d+=[i[1]]
  elif i[1]==a:e+=[i[0]]
print((set(d)&set(e)==set())*'IM'+'POSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ 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)
q = deque([0])
dis = [-1] * n
dis[0] = 0
while q:
  d = q.popleft()
  for node in g[d]:
    if dis[node] == -1:
      q.append(node)
      dis[node] = dis[d] + 1
if dis[n - 1] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
#setで殴る
n,m=map(int,input().split())
s=[set()for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  s[a-1].add(b)
for i in s[0]:
  if n in s[i-1]:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

def main():
	n, m = map(int,input().split())
	s=set()
	t=set()
	for _ in range(m):
		a, b = map(int, input().split())
		if a == 1:
			s.add(b)
		elif b == n:
			t.add(a)
	for i in s:
		if(i in t):
			print('POSSIBLE')
			exit()
	print('IMPOSSIBLE')

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

Submission status: Accepted

Solution code:
import copy
import sys
import math

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = copy.deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			sys.exit()
	print('IMPOSSIBLE')


def listtodict(a):
	b = {}
	for i in a:
		try:
			b[i] += 1
		except:
			b[i] = 1
	return b

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
a=g[0]
for i in a:
	if N-1 in g[i]:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import numpy as np

n, m = list(map(int, input().split()))
ablist = [list(map(int, input().split())) for _ in range(m)]

from1 = np.zeros(n, dtype=int)
ton = np.zeros(n, dtype=int)

for ab in ablist :
    if ab[0] == 1 :
        from1[ab[1]-1] = 1
    elif ab[1] == n :
        ton[ab[0]-1] = 1

if sum(from1*ton) > 0 :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    s, d = set(), set()  # start, destination
    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            s.add(b)  # 1 to X
        elif b == n:
            d.add(a)  # X to n
    # if the same X in both s & d -> possible
    print("POSSIBLE" if s & d else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

sp = [False for _ in range(N + 1)]
pg = [False for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    if a == N:
        pg[b] = True
    if b == N:
        pg[a] = True
    if a == 1:
        sp[b] = True
    if b == 1:
        sp[a] = True

for i in range(1, N + 1):
    if pg[i] and sp[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from_1 = [False]*N
to_N = [False]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b-1] = True
    elif b == N:
        to_N[a-1] = True
for i in range(1, N):
    if from_1[i] and to_N[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

INF = 10**12
N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
dist = [INF]*N
q = deque([(0, 0)])
while q:
    v, d = q.popleft()
    dist[v] = d
    for u in E[v]:
        if dist[u] == INF:
            q.append((u, d+1))
print('POSSIBLE' if dist[N-1] == 2 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict

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

import sys

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


if 1 not in teiki:
    print('IMPOSSIBLE')
    sys.exit()

for i in teiki[1]:
    if i in teiki and N in teiki[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split(' '))
route={ int(i):[] for i in range(N) }
for i in range(M):
  a,b=map(int,input().split(' '))
  route[a-1].append(b-1)
  route[b-1].append(a-1)
ans='IMPOSSIBLE'
for island in route[0]:
  if N-1 in route[island]:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
N,M = map(int,input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int,input().split())
    d[a].append(b)
for i in d[1]:
    if N in d[i]:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

A = []
B = [0]*(N+1)
for a,b in ab:
  if a==1:
    A.append(b)
  if b==N:
    B[a]=1

for a in A:
  if B[a]==1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
ab = []
for _ in range(M):
  _ab = map(int, raw_input().split())
  ab.append(_ab)
  
sorted_a = sorted(ab, key=lambda x:x[0])
sorted_b = sorted(ab, key=lambda x:x[1])

from_1 = set([b for a, b in sorted_a if a == 1])
to_N = set([a for a, b in sorted_b if b == N])

if len(from_1 & to_N) > 0:
  print 'POSSIBLE'
else:
  print 'IMPOSSIBLE'

Submission status: Accepted

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

for i in range(N):
    if((1,i)in s and (i,N) in s):
        print("POSSIBLE")
        exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n,m = (int(i) for i in input().split())
uf = UnionFind(n-1)
for i in range(m):
  a,b = (int(i) for i in input().split())
  if a == 1 or b ==n: uf.union(a-1,b-1)

if uf.same_check(0,n-1): print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
heapq.heapify(cand_1)
heapq.heapify(cand_2)


while len(cand_1) != 0 and len(cand_2) != 0:
    if cand_1[0] < cand_2[0]:
        heapq.heappop(cand_1)
    elif cand_1[0] > cand_2[0]:
        heapq.heappop(cand_2)
    else:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

# 実はdicts[0], dicts[N-1]だけあれば十分
dicts = [set() for _ in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dicts[a].add(b)
    dicts[b].add(a)

# 島1 -> どこかの島 -> 島Nというルートが可能
if dicts[0] & dicts[N-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [[-1]*2 for i in range(N)]
for _ in range(M):
    a, b = sorted(map(int, input().split()))
    if a == 1:
        if X[b][1] > 0:
            print("POSSIBLE")
            break
        else:
            X[b][0] = 1
    if b == N:
        if X[a][0] > 0:
            print("POSSIBLE")
            break
        else:
            X[a][1] = 1
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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


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

    for i in range(m):
        ai, bi = map(int, input().split())

        if ai == 1:
            is_included_1.add(bi)
        elif bi == 1:
            is_included_1.add(ai)

        if ai == n:
            is_included_n.add(bi)
        elif bi == n:
            is_included_n.add(ai)

    if len(is_included_1 & is_included_n) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b = map(int,input().split(" "))
ar = [[] for i 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])
for r in ar[1]:
    if a in ar[r]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

for i in range(M):
    ai, bi = input().split(' ')
    if ai == '1':
        a.append(bi)
    if bi == str(N):
        b.append(ai)
if len(set(a) & set(b)) > 0:
    print("POSSIBLE")
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque
def dfs(path):
    global visited, A
    q = deque([])
    q.append(path)
    for d in A[1]:
        q.append(d)
    while q:
        p = q.pop()
        for d in A[p]:
            if visited[d] == True:
                pass
            else:
                visited[d] = True


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)
    visited = [False] * (N+1)
    dfs(1)
    if visited[N]:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
x=[0]*(N+1)
y=[0]*(N+1)
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x[b]=1
    if b==N:
        y[a]=1
for i in range(N+1):
    if x[i]==1 and y[i]==1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
Liner = defaultdict(lambda: [])
def inpl(): return [int(i) for i in input().split()]
import sys
N, M = inpl()
for _ in range(M):
    a, b = inpl()
    Liner[a].append(b)
    Liner[b].append(a)
if not Liner[1]:
    print('IMPOSSIBLE')
    sys.exit()
for i in Liner[1]:
    if N in Liner[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.add(b)
    elif b == n:
        e.add(a)
        
print('IM' * (1 - len(s & e)) + 'POSSIBLE')

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/arc079/tasks/arc079_a


def solve():
    from_start = set()
    to_end = set()
    n, m = map(int, input().split())

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            from_start.add(b)
        elif b == n:
            to_end.add(a)

    if len(from_start & to_end) == 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l1=[False]*(N+1)
l2=[False]*(N+1)


for i in range(M):
    a, b = map(int, input().split())
    if a==1:
        l1[b]=True
    elif b==N:
        l2[a]=True
        
fl=False
for i in range(N):
    if l1[i] and l2[i]:
        fl=True
    
if fl:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]

first = dict()
for a, b in ab:
    if a == 1:
        first[b] = 1

for a, b in ab:
    if b == N:
        if a in first:
            print("POSSIBLE")
            exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

L = [None] * M

for i in range(M):
    a, b = [int(x) for x in input().split()]
    L[i] = (a, b)

set1 = set()
set2 = set()

for l in L:
    a, b = l[0], l[1]
    if a == 1:
        set1.add(b)
    if b == N:
        set2.add(a)

if set1.isdisjoint(set2):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

L = [0 for i in range(N)]

for i in range(M):
	a, b = list(map(int, input().split()))
	if a == 1:
		L[b - 1] += 1
	elif b == 1:
		L[a - 1] += 1
	elif a == N:
		L[b - 1] += 1
	elif b == N:
		L[a - 1] += 1
	else:
		pass

if L.count(2) >= 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

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

is1 = [False] * (n + 1)
isN = [False] * (n + 1)

for i in range(m):
    a, b = map(int, input().split())
    if(a > b):
        a, b = b, a
    if(a == 1):
        is1[b] = True
    if(b == n):
        isN[a] = True

import sys

for i in range(2, n):
    if(is1[i] and isN[i]):
        print("POSSIBLE")
        sys.exit(0)

print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].add(b)
for x in table[0]:
    if N-1 in table[x]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

f = False
for i in l[0]:
    for j in l[i]:
        if j == n-1:
            f = True
            break
if f:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
f = lambda: map(int,input().split())

n,m = f()
s = [[] for _ in range(n)]
for _ in range(m):
    a, b = f()
    a-=1; b-=1
    s[a].append(b); s[b].append(a)
for i in s[0]:
    if n-1 in s[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
ed = defaultdict(lambda:False)
for i in range(M):
	a,b = inpl()
	if a == 1:
		if ed[b]:
			print('POSSIBLE')
			sys.exit()
		else:
			ed[b] = True
	elif b == N:
		if ed[a]:
			print('POSSIBLE')
			sys.exit()
		else:
			ed[a] = True

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = set()
for _ in range(M):
  a, b = reads()
  a, b = a-1, b-1
  edges.add((a, b))
  edges.add((b, a))

for k in range(N):
  if (0, k) in edges and (k, N-1) in edges:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# cook your dish here
n,m = map(int,input().split())
a = []

for i in range(m):
    l = list(map(int,input().split()))
    if l[0] == 1:
        a.append(l[1])
    elif l[1] == n:
        a.append(l[0])

b = list(set(a))
if len(a)==len(b):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
line = input().split()
n = int(line[0])
m = int(line[1])

path = [[] for _ in range(n)]
for _ in range(m):
    line = input().split()
    a = int(line[0])-1
    b = int(line[1])-1
    path[a].append(b)

def dfs(i, s):
    if i==n-1:
        if s==2:
            return True
        else:
            return False

    for e in path[i]:
        if dfs(e, s+1):
            return True
    return False

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

Submission status: Accepted

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

Submission status: Accepted

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

stomid = [0]*n
midtog = [0]*n

for i in range(m):
	f,t = map(int,raw_input().split())
	if f == 1:
		stomid[t-1] = 1

	elif t == n:
		midtog[f-1] = 1 

for i in range(n):
	if stomid[i] == midtog[i] == 1 :
		print 'POSSIBLE'
		quit()

print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(set)
for i in range(m):
  a, b = list(map(int, input().split()))
  d[a].add(b)
  d[b].add(a)
if d[1]&d[n]:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

a = []
b = []
for i in range(m):
    aa,bb = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
c = []
d = []
for i in range(m):
    if a[i] == 1:
        c.append(b[i])
    elif a[i] == n:
        d.append(b[i])
    elif b[i] == n:
        d.append(a[i])

ans = 'IMPOSSIBLE'
c = set(c)
d = set(d)

if len(c&d) >= 1:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
for i in range(0,M):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)

pos=0
i=0
g=[0 for i in range(0,200000)]
e=[]
f=[]
k=0
l=0
while i < M and pos == 0:
	if a[i] == 1:
		g[b[i]] = 1
	if b[i] == 1:
		g[a[i]] = 1
	i=i+1
i=0
while i < M and pos == 0:
	if a[i] == N:
		if g[b[i]] == 1:
			pos=1
	if b[i] == N:
		if g[a[i]] == 1:
			pos=1
	i = i + 1
if pos == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
nm = list(map(int, input().split()))
ships = []
for i in range(nm[1]):
    ships.append(list(map(int, input().split())))

first = []
second = []

for i in ships:
    if(i[0] == 1):
        first.append(i[1])
    if(i[1] == nm[0]):
        second.append(i[0])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ab = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
    ab1 = [b for a, b in ab if a == 1]
    ab2 = [a for a, b in ab if b == N]
    print('POSSIBLE' if len(set(ab1) & set(ab2)) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().split()]
f = set()
t = set()
ans = False
for i in range(m):
  a,b = [int(x) for x in input().split()]
  if a == 1:
    f.add(b)
  if b == n:
    t.add(a)
for i in f:
  if i in t:
    ans = True
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = True

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:


        return array_result

arr_data = getinputdata()

#島数
n = arr_data[0][0]
m = int(arr_data[0][1])

arr01 = []
arr02 = []
for i in range(1, 1 + m):

    if arr_data[i][0] == "1":
        
        arr01.append(arr_data[i][1])

    if arr_data[i][1] == n:
        
        arr02.append(arr_data[i][0])


print("POSSIBLE" if len(list(set(arr01) & set(arr02))) == 1 else "IMPOSSIBLE")

Submission status: Accepted

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


ichi = set()
enu = set()

for _ in range(m):
	a, b = list(map(int, input().split()))
	if a == 1:
		ichi.add(b)
	elif a == n:
		enu.add(b)
	elif b == 1:
		ichi.add(a)
	elif b == n:
		enu.add(a)

if ichi & enu != set():
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

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

for i in trans[1]:
    if N in trans[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

R = defaultdict(set)

for i in range(M):
    a,b = map(int,input().split())
    R[a].add(b)
    
isok = False
for r in R[1]:
    if N in R[r]:
        isok = True
        break
        
if isok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
f, n = set(), set()
for i in range(M):
    temp = inpl()
    if 1 in temp:
        f.add(temp[1])
    if N in temp:
        n.add(temp[0])
if len(f & n) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
f, n = [], []
for i in range(M):
    temp = inpl()
    if 1 in temp:
        f.append(temp[1])
    if N in temp:
        n.append(temp[0])
if len(set(f) & set(n)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, heapq
sys.setrecursionlimit(10 ** 7)
pinf = float("inf")
ninf = -float("inf")
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
ans = "IMPOSSIBLE"
n -= 1
for e in edge[0]:
    if n in edge[e]:
        ans = "POSSIBLE"
print(ans)

Submission status: Accepted

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

First=set()
Second=set()

for i in range(M):
  a,b=map(int,input().split())
  if a==1 or b==1:
    First.add(max(a,b))
  elif a==N or b==N:
    Second.add(min(a,b))

Ans= First & Second

if len(Ans):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sb=[0]*(n+1)
db=[0]*(n+1)
for _ in range(m):
    s,d=map(int,input().split())
    if s==1:
        sb[d]=1
    if d==n:
        db[s]=1

for i in range(n):
    if sb[i]==1 and db[i]==1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')