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: Runtime Error

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


connections = dict()
answer = {
    'true': 'POSSIBLE',
    'false': '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 e in island_N:
        print(answer['true'])
    else:
        print(answer['false'])

Submission status: Runtime Error

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


connections = {}
answer = {
    'true': 'POSSIBLE',
    'false': 'IMPOSSIBLE'
}


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

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


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


for e in connections[1]:
    if e in connections[n]:
        print(answer['true'])
    else:
        print(answer['false'])

Submission status: Runtime Error

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

m = int(m)


connections = {}
answer = {
    'true': 'POSSIBLE',
    'false': 'IMPOSSIBLE'
}


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

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


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


for e in connections['1']:
    if e in connections[n]:
        print(answer['true'])
    else:
        print(answer['false'])

Submission status: Runtime Error

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

i = 0
j = 0
to = starts[i][1]
fr = ends[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: Runtime Error

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

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: Runtime Error

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

Submission status: Runtime Error

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())
	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 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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for i  in range(size)]
    def find(self,x):
        if(self.table[x]<0):
            return x
        else :
            self.table[x]=self.find(self.table[x])
            return self.table[x]

    def union(self,x,y):
        s1 = self.find(x)        
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2]=s1
        return


N,M=map(int,input().split())
uf=UnionFind(N+1)
for i in range(M):
    a,b=map(int,input().split())
    uf.union(a,b)

if(1==uf.find(N)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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)


l1 = len(cand_1)
l2 = len(cand_2)
i = 1
j = 1
e1 = heapq.heappop(cand_1)
e2 = heapq.heappop(cand_2)

if e1 == e2:
    ans = "POSSIBLE"
while i < l1 and j < l2:
    if e1 == e2:
        ans = "POSSIBLE"
        break
    elif e1 > e2:
        e2 = heapq.heappop(cand_2)
        j += 1
    else:
        e1 = heapq.heappop(cand_1)
        i += 1
print(ans)

Submission status: Runtime Error

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: Runtime Error

Solution code:
n,m=map(int, input().split())
main_list=list()
list2=list()
for i in range(m):
    a,b=map(int, input().split())
    list2.append(a)
    list2.append(b)
    main_list.append(list2)
    list2=[]
for i in range(m):
    if main_list[i][0]==1:
        for j in range(m):
            if (main_list[i][1]==main_list[j][0])and(main_list[j][1]==n):
                k=0
                print("POSSIBLE")
                break
if k!=0:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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,M)]
print(g)
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
print(g)
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: Runtime Error

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 n in f[vv]:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
k = int(input())
n = 50
m = (n - 1) * (k + 1) + 1


series = str(m)
for i in range(n):
    series = series + " 0"

print(str(n))
print(series)

Submission status: Runtime Error

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'

else:
 print 'IMPOSSIBLE'

Submission status: Runtime Error

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

f = dict()
for i in range(m):
    a, b = map(int, raw_input().split())
    f[a] = b

if m == 1:
    print("IMPOSSIBLE")
    exit()

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

Submission status: Runtime Error

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] == 0:
        probInit.add(edge[1])

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

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

Submission status: Runtime Error

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

 
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: Runtime Error

Solution code:
import sys;
lines = sys.stdin.readlines();
n = {};
can = "";
max = 1;
for i, line in enumerate(lines):
    start,goal = line.split();
    start = int (start);
    goal  = int (goal);
    if not start in n :
        n[start] = [];
    if (max < start):
        max = start;
    if (max < goal):
        max = goal;
    n[start].append(goal);
if(n.has_key(1)):
    for w in n[1]:
        if w is not None and w == max:
            can = "POSSIBLE";
            break;
        elif w is not None and w in n:
            for i in n[w]:
                if i == max:
                    can = "POSSIBLE";
                    break;

if can == "":
    print ("IMPOSSIBLE");
else:
    print(can);

Submission status: Runtime Error

Solution code:
K = int(input())
a = 0
b = 0

for i in range(1, 51):
	if (K - K % i) / i + i - 1 >= 1000 + 10**16:
		break

	b = int(K % i)
	a = int((K - b) / i)
	N = i
	


list = [0] * N
j = 0



while (j <= N - b - 1) :
	list[j] = N + a - b - 1
	j += 1

while (j > N - b - 1 and j <= N - 1):
	list[j] = 2 * N - b
	j += 1


list = map(str, list)
print(' '.join(list))

Submission status: Runtime Error

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
	elif b == n:
		d[a] = 1

for i in range(1,m+1):
	if s[i] == 1 and d[i] == 1:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#coding:utf-8

import sys

teikibin = {}
ans = False

n, m = sys.stdin.readline().strip().split(" ")
n = int(n)
m = int(m)

for i in range(m):
    a, b = sys.stdin.readline().strip().split(" ")
    a = int(a)
    b = int(b)
    
    if a in teikibin:
        teikibin[a].append(b)
    else:
        teikibin[a] = [b]

    if a == 1:
        target = b
        if b in teikibin[1]:
            if b in teikibin.keys():
                if n in target[b]:
                    ans = True

        #if target in teikibin.keys():
        #    if n in teikibin[target]:
        #        ans = True
    else:
        target = a

        if 1 in teikibin.keys():
            if a in teikibin[1]:
                if target in teikibin.keys():
                    if n in teikibin[target]:
                        ans = True

        #target = a
        #if 1 in teikibin.keys():
        #    if target in teikibin[1]:

        #if target in teikibin.keys():
        #    if n in teikibin[target]:
        #        ans = True


if (not ans):
    print"IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Runtime Error

Solution code:
#coding:utf-8

import sys

teikibin = {}
ans = False

n, m = sys.stdin.readline().strip().split(" ")
n = int(n)
m = int(m)

for i in range(m):
    a, b = sys.stdin.readline().strip().split(" ")
    a = int(a)
    b = int(b)
    
    if a in teikibin:
        teikibin[a].append(b)
    else:
        teikibin[a] = [b]

    if a == 1:
        target = b
        if b in teikibin[1]:
            if b in teikibin.keys():
                if n in target[b]:
                    ans = True

        #if target in teikibin.keys():
        #    if n in teikibin[target]:
        #        ans = True
    else:
        target = a

        if 1 in teikibin.keys():
            if a in teikibin[1]:
                if target in teikibin.keys():
                    if n in teikibin[target]:
                        ans = True

        #target = a
        #if 1 in teikibin.keys():
        #    if target in teikibin[1]:

        #if target in teikibin.keys():
        #    if n in teikibin[target]:
        #        ans = True


if (not ans):
    print"INPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Runtime Error

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: Runtime Error

Solution code:
n = int(input())
ans = list(map(str,range(1,n+1)))
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

K = int(input())
K = K

# astypeを入れないとおかしくなっちゃう
a = np.ones(50).astype(np.int64)*(49) + (K)//50

if K%50 != 0:
    a[:K%50] += 51 - (K%50)
    a[K%50:] -= (K%50)
else:
    pass
              
result = "50\n{}".format(a[0])
for a_ in a[1:]:
    result += (" {}".format(int(a_)))
print(result)

Submission status: Runtime Error

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: Runtime Error

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

s = sum(A) - N*(N-1)
m = sum(list(map(lambda x: (x+s)//N, A)))
while m > s:
    s = m
    m = sum(list(map(lambda x: (x+s)//N, A)))
else:
    print(m)

Submission status: Runtime Error

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

s = sum(A) - N*(N-1)
m = list(map(lambda x: (x+s)//N, A))
while m > s:
    s = m
    m = list(map(lambda x: (x+s)//N, A))
else:
    print(m)

Submission status: Runtime Error

Solution code:
n=int(raw_input())
if n%2==0:
    print 2
    print n/2+1,n/2+1
else:
    print 2
    print (n-1)/2,(n-1)/2+3

Submission status: Runtime Error

Solution code:
def show1(n, ans):
    for i in xrange(n):
        print ans[i],
    print

def show2(n, m, l, ans):
    for i in xrange(l):
        print ans[i] + m + 1,
    for i in xrange(l, n):
        print ans[i] + m ,
    print

k = int(raw_input())
n = 50
ans = [0] * n
print n
if k <= n:
    for i in xrange(k):
        ans[i] = n - i
    show1(n, ans)
else:
    ans = range(50, 0, -1)
    m = k / 50 - 1
    l = k % 50
    show2(n, m, l, ans)

Submission status: Runtime Error

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

A = set({})
B = set({})
for j in range(N-1):
    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: Runtime Error

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