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:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append([a, b])
    from_one = set()
    from_n = set()
    for i in range(m):
        if edges[i][0] == 1:
            from_one.add(edges[i][1])
        if edges[i][1] == n:
            from_n.add(edges[i][0])
    common = from_one & from_n
    print("POSSIBLE" if len(common) > 0 else "IMPOSSIBLE")

main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

from1 = set()
gotoN = set()

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

	if b == 1:
		from1.add(a)
	elif b == N:
		gotoN.add(a)

res = from1 & gotoN

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")

Submission status: Accepted

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

from1 = []
gotoN = []

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

res = set(from1) & set(gotoN)

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")

Submission status: Accepted

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

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

from1 = []
gotoN = []

for m in range(M):
    a, b = list(map(int, input().split()))
    if a==1:
        from1.append(b)
    if b==N:
        gotoN.append(a)

can = set(from1) & set(gotoN)

if len(can) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
[N, M] = [int(x) for x in input().split()]
list_all = []
for i in range(M):
	list_all.append([int(x) for x in input().split()])
	
list_mid = []
for i in range(M):
	if 1 in list_all[i]:
		list_mid.append(list_all[i][1])
	if N in list_all[i]:
		list_mid.append(list_all[i][0])

if len(list_mid) == len(set(list_mid)):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

f = dict()
for i in range(m):
    a, b = map(int, raw_input().split())
    if a in f:
        f[a].append(b)
    else:
        f[a] = [b]
if m < 2:
    print("IMPOSSIBLE")
    exit()

for k, v in f.iteritems():
    if k == 1:
        for vv in v:
            if vv not in f:
                continue
            if n in f[vv]:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

N, M = map(int, raw_input().split())
a = []
for i in xrange(M):
    a.append(map(int, raw_input().split()))

s1=set()
s2=set()
for i in xrange(M):
    if a[i][0]==1:
        s1.add(a[i][1])
    if a[i][1]==N:
        s2.add(a[i][0])
if s1 & s2:
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
x = input().split(" ")
n = int(x[0])
m = int(x[1])

probInit = set([])
probEnd  = set([])

for i in range(m):
    edge = input().split(" ")
    if edge[0] == "1":
        probInit.add(edge[1])

    if edge[1] == str(n):
        probEnd.add(edge[0])

sec = probEnd.intersection(probInit)
if (len(sec) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
import sys
N, M = list(map(int, input().split()))
ls = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    ls[a].append(b)

if len(ls[1]) == 0:
    print('IMPOSSIBLE')
    sys.exit()

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

Submission status: Accepted

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

from_1 = [0 for i in range(N)]
to_N = [0 for i in range(N)]

for f in ferry:
    if f[0]==1:
        from_1[f[1]-1] = 1
    if f[1]==N:
        to_N[f[0]-1] = 1


flag = 0

for k in range(N):
    if from_1[k]==1 and to_N[k]==1:
        print('POSSIBLE')
        flag = 1
        break

if flag==0:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
N, M = map(int, input().split())
A = [ 0 for tmp in range(N) ]
B = [ 0 for tmp in range(N) ]
for tmp in range(M):
    a, b = map(int, input().split())
    if a == N or b == N:
        c = a if a != N else b
        B[c-1] = 1
    if a == 1 or b == 1:
        c = a if a != 1 else b
        A[c-1] = 1

for tmp in range(N):
    if A[tmp] and B[tmp]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = [int(s) for s in raw_input().split(" ")]
routes = []
for i in xrange(m):
    routes.append([int(s) for s in raw_input().split(" ")])
x = set([r[1] for r in routes if r[0] == 1])
y = set([r[0] for r in routes if r[1] == n])
print "POSSIBLE" if x & y else "IMPOSSIBLE"

Submission status: Accepted

Solution code:
[n, m] = [int(num) for num in input().split()];
a = [];
b = [];

for i in range(m):
	[t1, t2] = [int(num) for num in input().split()];
	a.append(t1);
	b.append(t2);

start = [];
end = [];
for i in range(n):
	start.append(False);
	end.append(False);
	
for i in range(m):
	if a[i] == 1:
		start[b[i]] = True;
	elif b[i] == n:
		end[a[i]] = True;
		
flag = False;
for i in range(n):
	if start[i] & end[i]:
		flag = True;
		
if flag:
	print('POSSIBLE');
else:
	print('IMPOSSIBLE');

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
g=[[] for i in range(2*10**5+1)]
for i in range(m):
	a,b=map(int,raw_input().split())
	g[a].append(b)
	g[b].append(a)
for i in g[1]:
	for j in g[i]:
		if j==n:
			print "POSSIBLE"
			exit(0)
print "IMPOSSIBLE"

Submission status: Accepted

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

s = [0]*(n+1)
d = [0]*(n+1)

for i in range(m):
	a, b = [int(x) for x in input().split()]
	if a == 1:
		s[b] = 1
		if d[b] == 1:
			print('POSSIBLE')
			break
	elif b == n:
		d[a] = 1
		if s[a] == 1:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#ARC079C

n,m=map(int,raw_input().split())
l=[]
for i in xrange(m):
 a,b=map(int,raw_input().split())
 l.append([a,b])
s1=set()
s2=set()
for i in xrange(m):
 if l[i][0]==1:
  s1.add(l[i][1])
 if l[i][1]==n:
  s2.add(l[i][0])
if s1&s2:
 print 'POSSIBLE'
else:
 print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
n,m,*T=map(int,open(0).read().split());*S,=zip(T[::2],T[1::2]);s=lambda e:set(s[e<2]for s in S if e in s);print("IM"*(len(s(1)&s(n))<1)+"POSSIBLE")

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    a = []
    b = []
    for i in range(M):
        tmp_a, tmp_b = list(map(int, input().split()))
        a.append(tmp_a)
        b.append(tmp_b)

    c = set([b[i] for i in range(0, M) if a[i] == 1])

    for i in range(0, M):
        if a[i] in c and b[i] == N:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")

Submission status: Accepted

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

f = set()
t = set()

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

pos = "IMPOSSIBLE"

if f&t:
    pos = "POSSIBLE"

print(pos)

Submission status: Accepted

Solution code:
from sys import stdin
n,m = map(int,stdin.readline().split())
ans = 'IMPOSSIBLE'
di = set()
for i in xrange(m):
 x,y = map(int,stdin.readline().split())
 di.add((min(x,y),max(x,y)))
for i in xrange(2,n):
 fir = (1,i)
 sec = (i,n)
 if fir in di and sec in di:
  ans = 'POSSIBLE'; break
print ans

Submission status: Accepted

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

ax = []
bx = []
for _ in xrange(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        bx.append(b)
    if b == N:
        ax.append(a)
if len(set(ax) & set(bx)) > 0:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Submission status: Accepted

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 s:
        if n in w[i]:
            print("POSSIBLE")
            return 0
    print("IMPOSSIBLE")
    return 0
f()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[False]*200001
g=[False]*200001
r='POSSIBLE'
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        if g[b]:
            break
        s[b]=True
    elif b==n:
        if s[a]:
            break
        g[a]=True
else:
    r='IMPOSSIBLE'
print(r)

Submission status: Accepted

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

one_to_routes = set()
other_routes_contains_N = set()

for _ in range(M):
    a, b = map(int, input().split(' '))

    if a == 1:
        one_to_routes.add(b)
    elif b == N:
        other_routes_contains_N.add(a)

if one_to_routes.isdisjoint(other_routes_contains_N):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

    mid1 = [False]*(n+1)
    mid2 = [False]*(n+1)

    for _ in range(m):
        a, b = list(map(int, input().split(' ')))
        if a == 1:
            mid1[b] = True
        if b == n:
            mid2[a] = True

    for i in range(n+1):
        if mid1[i] and mid2[i]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = map(int,input().split())
from1 = [0]*(n+1)
ton = [0]*(n+1)
for i in range(m):
    a, b = map(int,input().split())
    if a == 1: from1[b] = 1
    if b == n: ton[a] = 1
for i in range(n+1):
    if from1[i] and ton[i]:
        print("POSSIBLE")
        break
else: print("IMPOSSIBLE")

Submission status: Accepted

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

A = set({})
B = set({})
for j in range(M):
    tmp = []
    tmp = [int(i) for i in input().split()]
    if tmp[0] == 1:
        A.add(tmp[1])
    elif tmp[1] == N:
        B.add(tmp[0])

if len(A.intersection(B)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    D = dd(list)

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

    for d in D[0]:
        if N-1 in D[d]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

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

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
paths = []
for _ in xrange(m):
	a, b = map(int, raw_input().split())
	paths.append((a, b))
hop2 = set()
for a, b in paths:
	if a == 1:
		hop2.add(b)
flag = 0
for a, b in paths:
	if a in hop2:
		if b == n:
			flag = 1
			break

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

Submission status: Accepted

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

for _ in range(M):
    a, b = map(int,input().split())
    if a == 1:
        route_1.add(b)
    elif b == N:
        route_N.add(a)

if route_1&route_N:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

def step(step_num, n, path, reachable):
    reachable[n] = 1
    step_num += 1

    if step_num > 2:
        return
    if not n in path:
        return

    for b in path[n]:
        if reachable[b]:
            continue
        step(step_num, b, path, reachable)

path = {}
for i in range(M):
    a, b = map(int, input().split())
    if a in path:
        path[a].append(b)
    else:
        path[a] = [b]

reachable = [0] * (N + 1)
step(0, 1, path, reachable)

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

Submission status: Accepted

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>2:
                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: Accepted

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

N, M = [int(n) for n in input().split()]
islands = {n:[] for n in range(1, N+1)}
result = "IMPOSSIBLE"

for m in range(M):
    a, b = [int(n) for n in input().split()]
    islands[a].append(b)
    islands[b].append(a)

ok_isl = set()
search_isl = [1]
next_isl = set()

loop = True
for x in range(2):
    for i in search_isl:
        if N in islands[i]:
            loop = False
            result = "POSSIBLE"            
        else:
            next_isl.update(islands[i])
    
    ok_isl = ok_isl.union(search_isl)
    
    search_isl = next_isl.difference(ok_isl)
    if len(search_isl) == 0:
        break

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

def main():
    N, M = map(int, input().split())
    A = []
    B = []
    d = {}

    for i in range(M):
        a, b = sorted(map(int, input().split()))
        if b in d:
            d[b] += [a]
        else:
            d[b] = [a]
    q = [N]
    cnt = 3
    while q and cnt > 0:
        cnt -= 1
        p = q
        q = []
        for i in p:
            if i == 1:
                print('POSSIBLE')
                return
            if i in d:
                q += d[i]
    print('IMPOSSIBLE')
    return
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a=[0]*(200001)


N = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(N[1])]


for i in x:
    if i[0]==1 :
        if a[i[1]]==1:
            print('POSSIBLE')
            quit()
        a[i[1]]=1
    if i[1]==N[0]:
        if a[i[0]]==1:
            print('POSSIBLE')
            quit()
        a[i[0]]=1

print('IMPOSSIBLE')
quit()

Submission status: Accepted

Solution code:
# coding: utf-8

def main():
    N, M = map(int, input().split())
    ships = set()
    for _ in range(M):
        a, b = map(int, input().split())
        ships.add((a, b))
        ships.add((b, a))
    for i in range(2, N):
        if (1, i) in ships and (i, N) in ships:
            return "POSSIBLE"
    else:
        return "IMPOSSIBLE"


print(main())

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    connect_to_1_set = set([])
    connect_to_N_set = set([])
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        if a == 1:
            connect_to_1_set.add(b)
        elif b == 1:
            connect_to_1_set.add(a)

        if a == N:
            connect_to_N_set.add(b)
        elif b == N:
            connect_to_N_set.add(a)

    if len(connect_to_1_set & connect_to_N_set) == 0:
        print "IMPOSSIBLE"
    else:
        print "POSSIBLE"



if __name__ == '__main__':
    main()

Submission status: Accepted

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(2)] for j in range(N+1)]
for i in range(M):
    a, b = rli()
    if(b == 1 or b == N):
        keiro[a][1 if b == 1 else 0] = True
    elif(a == 1 or a == N):
        keiro[b][1 if a == 1 else 0] = True

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

Submission status: Accepted

Solution code:
import collections
import sys

INF = sys.maxsize // 2


def solve(num_vs, adj_list, source, dest):
    visited = [False for _ in range(num_vs)]
    dist = [INF for _ in range(num_vs)]
    q = collections.deque()
    dist[source] = 0
    q.append(source)
    while q:
        s = q.popleft()
        if s == dest:
            return dist[dest] == 2
        for t in adj_list[s]:
            if not visited[t]:
                visited[t] = True
                q.append(t)
                dist[t] = dist[s] + 1
    return False


def main():
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = solve(n, adj_list, 0, n - 1)
    print("POSSIBLE" if res else "IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int, raw_input().split())
aa = set()
bb = set()
for _ in range(m):
  a,b = map(int, raw_input().split())
  a,b = min(a,b),max(a,b)
  if a == 1:
    aa.add(b)
  if b == n:
    bb.add(a)
for i in range(1,n+1):
  if i in aa and i in bb:
    print 'POSSIBLE'
    exit()
print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
import bisect

ans = "IMPOSSIBLE"
n, m = map(int, input().split())
ac = []
bc = []
for _ in range(m):
    a, b = map(int, input().split())
    if min(a, b) == 1:
        ac.append(max(a, b))
    elif max(a, b) == n:
        bc.append(min(a, b))
ac = list(sorted(ac))
bc = list(sorted(bc))
for c in ac:
    i = bisect.bisect_left(bc, c)
    if i < len(bc) and bc[i] == c:
        ans = ans[2:]
        break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# -*- coding: UTF-8 -*-

#n=int(input())
n,m=map(int,input().split())
a=set([])
b=set([])

for i in range(m):
    u,v=map(int,input().split())
    if u==1:
        a.add(v)
    if v==n:
        b.add(u)

    

print('POSSIBLE' if a&b else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('c1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    possible = 'POSSIBLE'
    impossible = 'IMPOSSIBLE'
    n, m = read_int_list()
    c = Counter()
    res = impossible
    for i in range(m):
        a, b = read_int_list()
        if a == 1:
            c[b] += 1
        if b == n:
            c[a] += 1
        if c[a] == 2 or c[b] == 2:
            res = possible
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

N, M = list(map(int, sys.stdin.readline().rstrip().split()))


Ss = set()
Es = set()
for _ in range(M):
    a_orig, b_orig = list(map(int, sys.stdin.readline().rstrip().split()))
    for a, b in [(a_orig, b_orig), (b_orig, a_orig)]:
        if a== 1:
            Ss.add(b)
        if a == N:
            Es.add(b)

if len(Ss.intersection(Es)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
exit(0)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
one = [0 for i in range(n + 1)]
edges = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        one[b] = 1
    if b == 1:
        one[a] = 1
    else:
        edges.append((a, b))
for a, b in edges:
    if one[a] and b == n or one[b] and a == n:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for e in edges[0]:
    if any(c == N - 1 for c in edges[e]):
        print("POSSIBLE")
        quit()
print("IMPOSSIBLE")

Submission status: Accepted

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

memo = [False]*N
result = False

for i in range(M):
  a,b = map(int, input().split())
  if a == 1:
    result |= memo[b]
    memo[b] = True
  elif b == N:
    result |= memo[a]
    memo[a] = True

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

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import defaultdict

INF = 10 ** 20
MOD = 10 ** 9 + 7


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


def read():
    N, M = ILI()
    edges = defaultdict(list)
    for __ in range(M):
        a, b = ILI()
        edges[a].append(b)
        edges[b].append(a)
    return N, M, edges


def solve(N, M, edges):
    s_from_1 = set(edges[1])
    s_from_n = set(edges[N])
    set_and = s_from_1 & s_from_n
    ans = ""
    if len(set_and) == 0:
        ans = "IMPOSSIBLE"
    else:
        ans = "POSSIBLE"
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# C
import numpy as np
N, M = map(int, input().split())

alpha = np.zeros(N+1)
omega = np.zeros(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        alpha[b] = 1
    if b == N:
        omega[a] = 1
        
if (alpha*omega).sum() > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E1 = set()
EN = set()
for n in range(M):
    a, b = map(int, input().split())
    if a == 1:
        E1.add(b)
    if b == 1:
        E1.add(a)
    if a == N:
        EN.add(b)
    if b == N:
        EN.add(a)
for a in E1:
    if a in EN:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

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

a = [0] * (n + 1)
for _ in xrange(m):
	x, y = map(int, raw_input().split())
	if x > y:
		x, y = y, x
	if x == 1:
		a[y] += 1
	if y == n:
		a[x] += 1
for i in xrange(2, n):
	if a[i] == 2:
		print "POSSIBLE"
		sys.exit(0)
print "IMPOSSIBLE"

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in raw_input().split()]
s = set()
e = set()
for i in xrange(m):
    a, b = [int(_) for _ in raw_input().split()]
    if a == 1:
        e.add(b)
    if b == n:
        s.add(a)

if s & e:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**9
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N,M = LI()
    a = [LI() for _ in range(M)]
    t = set()
    s = set()
    for i,j in a:
        if i==1:
            t.add(j)
        elif i==N:
            s.add(j)
        if j==1:
            t.add(i)
        elif j==N:
            s.add(i)
    if t&s:
        return 'POSSIBLE'

    return 'IMPOSSIBLE'



print(main())

Submission status: Runtime Error

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

ng = max(0, sum(list_of_a)-(N-1)*N) - 1
ok = max(0, (max(list_of_a) - (N-1)) * N)
while ok - ng > 1:
    mid = (ok + ng) // 2
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count <= mid:
        ok = mid
    else:
        ng = mid

#'ok'-i (i=1..N) may be better

for i in range(0, 5 * N + 1):
    mid = ok - i
    if mid < 0:
        break
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count == mid:
        ans = mid

print(ans)

Submission status: Runtime Error

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

ng = max(0, sum(list_of_a)-(N-1)*N) - 1
ok = max(0, (max(list_of_a) - (N-1)) * N)
while ok - ng > 1:
    mid = (ok + ng) // 2
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count <= mid:
        ok = mid
    else:
        ng = mid

#'ok'-i (i=1..N) may be better

for i in range(0, 3 * N + 1):
    mid = ok - i
    if mid < 0:
        break
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count == mid:
        ans = mid

print(ans)