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: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)

            if d==N:
                break

            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist




def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    n,m=spaceinput()
    g=myGraph()

    for i in range(10**6):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),1)
    res=g.dijkstra(start=1)
    #print(res)
    if n in res and res[n]<=2:
        if res[n]==1:
            if len(set(g.adj[1]).union(g.adj[n]))>0:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
come=[]
for i in range(M):
  ab=list(map(int,input().split()))
  if ab[0]==1:
    if ab[1] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[1]]
  if ab[1]==N:
    if ab[0] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[0]]
 
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
s = [int(i) for i in s]
import numpy as np

N = s[0]
M = s[1]

FROM = np.array([])
TO = np.array([])
for i in range(M) : 
    s = input().split()
    s = [int(i) for i in s]
    FROM = np.append( FROM ,  s[0])
    TO = np.append(TO , s[1])

#1 から Nに行きたい
# N に行ける定期便を探す　仮に中間地点INDとする
IND = np.array([])
for i in range(M) : 
    if TO[i] == N :IND = np.append(IND , FROM[i])

FLAG = False
for i in range(M) : 
    if FROM[i] == 1 : 
        if TO[i] in IND : 
            FLAG = True
            break

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

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist




def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    n,m=spaceinput()
    g=myGraph()

    for i in range(10**6):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),1)
    res=g.dijkstra(start=1)
    #print(res)
    if n in res and res[n]<=2:
        if res[n]==1:
            if len(set(g.adj[1]).union(g.adj[n]))>0:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
ab=[]
for i in range(M):
  ab+=[list(map(int,input().split()))]
come=[]
go=[]
for i in range(M):
  if ab[i][0]==1:
    if ab[i][1] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[i][1]]
  if ab[i][1]==N:
    if ab[i][0] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[i][0]]
 
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
ab=[]
for i in range(M):
  ab+=[list(map(int,input().split()))]
come=[]
go=[]
for i in range(M):
  if ab[i][0]==1:
    come+=[ab[i][1]]
    if ab[i][1] in go:
      print("POSSIBLE")
      sys.exit()
  if ab[i][1]==N:
    go+=[ab[i][0]]
    if ab[i][0] in come:
      print("POSSIBLE")
      sys.exit()
 
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
s = [int(i) for i in s]
N = s[0]
M = s[1]

FROM = []
TO = []
for i in range(M) : 
    s = input().split()
    s = [int(i) for i in s]
    FROM.append(s[0])
    TO.append(s[1])

#1 から Nに行きたい

# N に行ける定期便を探す　仮に中間地点INDとする
IND = []
for i in range(M) : 
    if TO[i] == N :
        IND.append(FROM[i])
        

FLAG = False
for i in range(M) : 
    if FROM[i] == 1 : 
        if TO[i] in IND : 
            FLAG = True
            break

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

Submission status: Time Limit Exceeded

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

    MAP = [[0]*N for n in range(N)]

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

    for first in range(N):
        if MAP[0][first]==1 and MAP[first][N-1] == 1:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
ab=[]
for i in range(M):
  ab+=[list(map(int,input().split()))]
come=[]
go=[]
for i in range(M):
  if ab[i][0]==1:
    come+=[ab[i][1]]
  if ab[i][1]==N:
    go+=[ab[i][0]]
for i in range(len(come)):
  if come[i] in go:
    print("POSSIBLE")
    sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def f():
    n,m = map(int,input().split(" "))
    s = []
    w = [[] for i in range(n+2)]
    for i in range(m):
        a,b = map(int,input().split(" "))
        
        if a==1:
            s.append(b)
        if b==1:
            s.append(a)
        w[a].append(b)
        w[b].append(a)
    for i in range(m+1):
        if i in s and n in w[i]:
            print("POSSIBLE")
            return 0
    print("IMPOSSIBLE")
    return 0
f()

Submission status: Time Limit Exceeded

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(a): return "".join(list(map(str, a)))

N, M = rli()
keiro = [[False for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a, b = rli()
    keiro[a][b] = True
    keiro[b][a] = True

flag = False
for i in range(N):
    if(keiro[i][1] and keiro[i][N]):
        flag = True
if(flag):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if t>=2:
                    continue
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return True
                self.parent[q] = p
                next_set.append((q, t + 1))
        return False


N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if graph.bfs(start=1, goal=N, time=0, save=False):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, M = MI()
    
    # 1 -> ? -> N
    S = [0] * N
    for i in range(M):
        a, b = MI()
        if a == 1:
            S[b] += 1
        elif b == N:
            S[a] += 1
    
    for s in S:
        if s >= 2:
            print('POSSIBLE')
            return 
    print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [0]*n

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l[b] += 1
    elif b == n:
        l[a] += 1

for i in l:
    if i >= 2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [0]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a==1 or a==N: X[b-1]+=1
    if b==1 or b==N: X[a-1]+=1

print('POSSIBLE' if max(X)>=2 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*ab = map(int,read().split())

m = iter(ab)

s1 = set()
s2 = set()
for a,b in zip(m,m):
    a -= 1
    b -= 1
    if a==0: s1.add(b)
    if a==n-1: s2.add(b)
    if b==0: s1.add(a)
    if b==n-1: s2.add(a)

#print(s1,s2,s1&s2)    

if len(s1&s2):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    elif(a[1]==N):
        a_list.append(a[0])
    
if list(set(pass_1) & set(a_list)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for _ 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(1,n):
  if x[i] == 1 and y[i] == 1:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
edge=[[] for i in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
for i in edge[0]:
    for j in edge[i]:
        a.append(j)
    a.append(i)
print('POSSIBLE' if n-1 in a else 'IMPOSSIBLE')

Submission status: Accepted

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

near = [set([]) for _ in range(n)]
for a, b in ab:
    near[a - 1].add(b - 1)
    near[b - 1].add(a - 1)

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for x in d[1]:
        if N in d[x]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(main())

Submission status: Accepted

Solution code:
import sys


def main():
  n, m, *lst = map(int, sys.stdin.read().split())
  set1, setn = set(), set()
  for i, j in zip(*[iter(lst)] * 2):
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  print('POSSIBLE' if set1 & setn else 'IMPOSSIBLE')


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys


def main():
  n, m = map(int, sys.stdin.readline().split())
  lst = map(int, sys.stdin.read().split())
  set1, setn = set(), set()
  for i, j in zip(lst, lst):
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  if set1 & setn:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys


def main():
  n, m = map(int, sys.stdin.readline().split())
  set1, setn = set(), set()
  for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  if set1 & setn:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
set1, setn = set(), set()
for _ in range(m):
  i, j = map(int, sys.stdin.readline().split())
  if i in [1, n] or j in [1, n]:
    if i == 1:
      set1.add(j)
    if i == n:
      setn.add(j)
    if j == 1:
      set1.add(i)
    if j == n:
      setn.add(i)
if set1 & setn:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N, M = LI()
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = LI()
    A[i] -= 1
    B[i] -= 1


def solve(link):
    for i in link[0]:
        if N - 1 in link[i]:
            return "POSSIBLE"
    return "IMPOSSIBLE"


def main():
    link = [set() for _ in range(N)]
    for a, b in zip(A, B):
        link[a].add(b)
        link[b].add(a)
    
    ans = solve(link)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
for i in range(m):
    l = list(map(int,input().split(" ")))
    ar[l[0]-1].append(l[1]-1)
    ar[l[1]-1].append(l[0]-1)
for r in ar[0]:
    if n - 1 in ar[r]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
N,M=list(map(int,input().split()))
N_l=set()
one_l=set()
for i in range(M):
   A,B=list(map(int,input().split()))
   if A == 1:
      one_l.add(B)
   elif B==N:
      N_l.add(A)
if len(N_l & one_l) > 0:
   print("POSSIBLE")
else:
   print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(m)]
hub1=set()
hub2=set()
for i in li:
    if n in i:
        hub1.add(sum(i)-n)
    if 1 in i:
        hub2.add(sum(i)-1)
if hub1&hub2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split( ))
s1=set()
sn=set()
for _ in range(m):
    a,b=map(int, input().split( ))
    if a==1 and b not in s1:
        s1.add(b)
    elif b==1 and a not in s1:
        s1.add(a)
    if a==n and b not in sn:
        sn.add(b)
    elif b==n and a not in sn:
        sn.add(a)
if s1&sn:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
E=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
dist=[10**7]*n
dist[0]=0
seen=[0]*n
seen[0]=1
stack=deque([0])
while stack:
  u=stack.popleft()
  for v in E[u]:
    if seen[v]!=1:
      dist[v]=min(dist[u]+1,dist[v])
      seen[v]=1
      stack.append(v)
if dist[n-1]==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N, M = LI()
    V = [[]for _ in range(N)]
    for i in range(M):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    if L[N-1]==2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    return

def examD():
    K = I()
    N = 50
    A = [i for i in range(N)]
    for i in range(N):
        A[-1-i] +=((K-i+49)//N)
    print(N); print(" ".join(map(str,A)))
    return

def examE():
    N = I()
    A = LI()
    ans = 0
    while(True):
        cur = 0
        for i in range(N):
            cur += A[i]//N
        for i in range(N):
            A[i] = A[i]%N + cur-A[i]//N
        ans += cur
        if cur==0:
            break
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:
def main():
  N,M = map(int,input().split())
  ships = [list(map(int,input().split())) for i in range(M)]
  start, goal = set(), set()
  for i in range(M):
    if ships[i][0] == 1:
      start.add(ships[i][1])
    if ships[i][1] == N:
      goal.add(ships[i][0])
  flg = start & goal
  print("POSSIBLE" if flg else "IMPOSSIBLE")
 
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
from _collections import defaultdict
from functools import lru_cache

class Scanner():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def map_int():
        return [int(x) for x in Scanner.string().split()]
    def string_list(n):
        return [input() for i in range(n)]
    def int_list_list(n):
        return [Scanner.mapInt() for i in range(n)]
    def int_cols_list(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True

MOD = int(1e09) + 7

def main():
    N,M = Scanner.map_int()
    G = [[] for i in range(N)]
    for i in range(M):
        a,b = Scanner.map_int()
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in G[0]:
        for j in G[i]:
            if j == N-1:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = {}
for _ in range(m):
    a, b = map(int, input().split())
    if not a in ab:
        ab[a] = []
    if not b in ab:
        ab[b] = []
    ab[a].append(b)
    ab[b].append(a)

def dfs(i: int, l:list) -> bool:
    if i > 2:
        return False

    ret = False
    for _l in l:
        if _l == n:
            ret = True

        if _l > i:
           ret |= dfs(i+1, ab[_l])

    return ret

print("POSSIBLE" if dfs(1, ab[1]) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


N, M = inpl()
AB = [inpl() for i in range(M)]

n1 = []
nN = []

for a, b in AB:
    if a == 1:
        n1.append(b)
    elif b == N:
        nN.append(a)

n1 = set(n1)
nN = set(nN)

print('POSSIBLE' if len(n1 & nN) > 0 else 'IMPOSSIBLE')

Submission status: Accepted

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


connections = dict()
answer = 'IMPOSSIBLE'


def add_to_set(a, b):
    if a in connections:
        connections[a].add(b)
    else:
        connections[a] = set([b])

    if b in connections:
        connections[b].add(a)
    else:
        connections[b] = set([a])


for i in range(m):
    a, b = list(map(int, input().split()))
    add_to_set(a, b)

island_1 = connections.get(1)
island_N = connections.get(n)


for e in island_1:
    if island_N and e in island_N:
        answer = 'POSSIBLE'

print(answer)

Submission status: Accepted

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

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

for i in range(m):
  a, b = map(int, input().split())
  
  if a == 1:
    if islands[b-1] == 2:
      print('POSSIBLE')
      break
    islands[b-1] = 1
  if b == n:
    if islands[a-1] == 1:
      print('POSSIBLE')
      break
    islands[a-1] = 2
    
  if i == m-1:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# 10 5
# 1 2
# 1 3
# 1 4
# 8 10
# 1 8

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

ends = []
starts = []
possible = False
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        starts.append([a, b])
    elif b == n:
        ends.append([a, b])

starts.sort(key=lambda x: x[1])
ends.sort(key=lambda x: x[0])

if not (starts and ends):
    print("IMPOSSIBLE")
    import sys

    sys.exit()

i = 0
j = 0
while i != len(starts) and j != len(ends):
    to = starts[i][1]
    fr = ends[j][0]

    if to == fr:
        possible = True
        break

    if to < fr:
        i += 1
    elif fr < to:
        j += 1

while j != len(ends):
    fr = ends[j][0]
    if to == fr:
        possible = True
        break
    j += 1

while i != len(starts):
    to = starts[i][1]
    if to == fr:
        possible = True
        break
    i += 1

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

Submission status: Accepted

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
def main():
    N, M, *AB = map(int, open(0).read().split())
    from_1, to_N = set(), set()
    for a, b in zip(*[iter(AB)] * 2):
        if a == 1:
            from_1.add(b)
        if b == N:
            to_N.add(a)
    flg = from_1 & to_N  # intermediate point of both 1, N exists?
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()