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:
n,m = map(int,input().split())

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

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

lis[0].sort()

for i in lis[-1]:
  if i in lis[0]:
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

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


for i in lis[-1]:
  if i in lis[0]:
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ships.append(Ship(f, t))

# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0
# 探索予定島
search_list = [0]

# 新たな島に移動できたなら次も探索する
while len(search_list):
  now_island = search_list.pop(0)
  # 各到達可能な島ごとに移動シミュレーション
  if reachable_islands[now_island] == float('inf'):
      continue
  # 全ての船についてシミュレート
  for ship in ships:
    # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
    if now_island == ship.land_from \
       and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
      # 到達済の印をつける
      reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
      # 到着島を探索予定リストに追加
      search_list.append(ship.land_to)

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ships.append(Ship(f, t))

# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0
# 探索予定島
search_list = [0]

# 新たな島に移動できたなら次も探索する
while len(search_list):
  now_island = search_list.pop(0)
  # 各到達可能な島ごとに移動シミュレーション
  if reachable_islands[now_island] == float('inf'):
      continue
  # 全ての船についてシミュレート
  for ship in ships:
    # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
    if now_island == ship.land_from \
       and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
      # 到達済の印をつける
      reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
      # 到着島を探索予定リストに追加
      search_list.append(ship.land_to)

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] <= 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#2問目
# resultにそれぞれの深さの数を入れていく
N, M = map(int, input().split())
link = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)
visited = [-1 for i in range(N)]
Q = [0]
visited[0] = 0

#Qに要素がなくなるまで
while Q:
    #一番上の要素をpop
    v = Q.pop(0)
    for i in link[v]:
        if visited[i] == -1:
            visited[i] = visited[v] + 1
            Q.append(i)

if 0 <= visited[N-1] <= 2: print("POSSIBLE")
else: print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
class Ship:
    def __init__(self, land_from, land_to):
        self.land_from = land_from - 1
        self.land_to = land_to - 1

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

ships = []
for _ in range(M):
    f, t = map(int, input().split())
    ships.append(Ship(f, t))

# 到達可能島リストに変化があったか？
is_updated = True
# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0

# 新たな島に移動できたなら次も探索する
while is_updated:
    is_updated = False
    # 各到達可能な島ごとに移動シミュレーション
    for island_num in range(N):
        # 到達し得ない島ならシミュレーションをスキップ
        if reachable_islands[island_num] == float('inf'):
            continue
        # 全ての船についてシミュレート
        for ship in ships:
            # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
            if island_num == ship.land_from and reachable_islands[ship.land_to] == float('inf'):
                # 到達済の印をつける
                reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
                # 島が更新されたフラグを立てる
                is_updated = True

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a_n= []
b_n= []

for i in range(M):
  a,b= map(int,input().split())
  a_n.append(a)
  b_n.append(b)

def possibleroot(n,m):
  for i in range(M):
    if(a_n[i]== n and b_n[i]== m):
      return True
  else:
    return False
  
for j in range(2,N):
  if(possibleroot(1,j) and possibleroot(j, N)):
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a_n= []
b_n= []

for i in range(M):
  a,b= map(int,input().split())
  a_n.append(a)
  b_n.append(b)

i= 0
flag= 0

if(M== 1):
  print("IMPOSSIBLE")
else:
  while True:
    if(a_n[i]== 1):
      b= b_n[i]
      for j in range(M):
        if(a_n[j]== b and b_n[j]== N):
          print("POSSIBLE")
          flag= 1
          break
    if(flag== 1):
      break
    elif(i== M- 1):
      print("IMPOSSIBLE")
      break
    i+= 1

Submission status: Time Limit Exceeded

Solution code:
import collections

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

q = collections.deque()
for i in range(m):
    if s[i][0] == 1:
        q.append(s[i][1])

for i in s:
    for j in q:
        if j in i and n in i:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import collections

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

q = collections.deque()
for i in range(m):
    if s[i][0] == 1:
        q.append(s[i][1])

for i in  q:
    if [i,n] in s or [n,i] in s:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    G[a].append(b)
    G[b].append(a)

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
if dfs(G, N, 0)[-1] > 2 or dfs(G, N, 0)[-1] == -1:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Time Limit Exceeded

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

candidate = []
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in candidate:
            print('POSSIBLE')
            exit()
        else:
            candidate.append(b)
    if b==n:
        if a in candidate:
            print('POSSIBLE')
            exit()
        else:
            candidate.append(a)
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque([1])
dist = [0] * (n + 1)
dist[1] = 0

while q:
    if max(dist) > 2:
        break
    node = q.popleft()
    after = graph[node]

    for a in after:
        q.append(a)
        if a == n:
            dist[a] = dist[node] + 1
            break
        else:
            dist[a] = dist[node] + 1

print("POSSIBLE" if dist[n] == 1 or dist[n] == 2 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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


def dfs(now, count):
    if count > 2:
        pass
    elif visit[n] == 0:
        visit[now] = 1
        for x in graph[now]:
            dfs(x, count + 1)


flag = False
if ab[0][0] == 1:
    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    visit[1] = 1

    dfs(1, 0)

    if visit[n] == 1:
        flag = True

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

Submission status: Time Limit Exceeded

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


def dfs(now, count):
    if count > 2:
        pass
    else:
        visit[now] = 1
        for x in graph[now]:
            dfs(x, count + 1)


flag = False
if ab[0][0] == 1:
    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    visit[1] = 1

    dfs(1, 0)

    if visit[n] == 1:
        flag = True

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append([b,n])
  if b==n:
    tempb.append([a,b])
if len(temp)>=1 and ans==0:
  """
  c = [x for x in tempb if x in templ]
  if len(c)>=1:
    print("POSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
templ=[0]*m
temp=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append([b,n])
if len(temp)>=1 and ans==0:
  c = [x for x in temp if x in templ]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
templ=[0]*m
temp=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
if len(temp)>=1 and ans==0:
  for i in range(0,m):
    if templ[i][0] in temp:
      if templ[i][1]==n:
        print("POSSIBLE")
        break
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(M)]
ans = "IMPOSSIBLE"
for n in range(1,N):
  if ([1,n] in s) and ([n,N] in s):
    ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(M)]
relay_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[1] for X in s if X[0] in relay_candidate]
if N in goal_candidate:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
for m in range(M):
  if s[m][0] == 1:
    relay_point = s[m][1]
    for m2 in range(m+1, M):
      if (s[m2][0] == relay_point) and ( s[m2][1] == N):
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Time Limit Exceeded

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

ne = []
for i in ab:
    if i[0] == "1":
        ne += [i[1]]

for j in ab:
    if j[0] in ne and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ab = sorted(ab)
firsts = []
nokori = copy.copy(ab)

for i in ab:
    if i[0] == "1":
        firsts += [i]
        nokori.remove(i)
    else:
        break

for i in firsts:
    for j in nokori:
        if j[0] == i[1] and j[1] == str(N):
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ab = sorted(ab)

for i in ab:
    if i[0] == "1":   
        for j in ab:
            if j[0] == i[1] and j[1] == str(N):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in ab:
    if i[0] == "1":   
        for j in ab:
            if j[0] == i[1] and j[1] == str(N):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = set()
B = set()
for _ in range(m):
    x = list(map(int,input().split()))
    if x[0]==1:
        A = A|set(x)
    elif x[1]==n:
        B = B|set(x)
if len(A&B)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

n = len(ab)

for i in range(n):
    if ab[i][1] != N:
        continue
    for j in range(n):
       if ab[i][0] == ab[j][1] and ab[j][0] == 1:
           print('POSSIBLE')
           exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
ab= [list(map(int,input().split())) for i in range(M)]

d = deque()

for i in range(len(ab)):
    if ab[i][1] == N:
        d.append(ab[i][0])

for i in range(len(d)):
    for j in range(len(ab)):
        if ab[j][0] == 1 and ab[j][1] == d[i]:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

x = []

for i in range(len(ab)):
    if ab[i][1] == N:
        x.append(ab[i][0])

for i in range(len(x)):
    for j in range(len(ab)):
        if ab[j][0] == 1 and ab[j][1] == x[i]:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

for i in starts:
    if i in goals:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
pos = False
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        if route[j][0] in temp:
            pos = True
            break
print("POSSIBLE") if pos else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
pos = False
for i in range(fune):
    if route[i][0] == 1:
        for j in range(fune):
            if route[j][1] == island:
                if route[i][1] == route[j][0]:
                    pos = True
                    break
        else:
            continue
        break
print("POSSIBLE") if pos else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [[0, 0]] * m
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == n:
        ab[i] = [a, b]
contain_one = [j for i, j in ab if i == 1]
string_ab = [str(k)+str(l) for k, l in ab]

for b in contain_one:
    if str(b)+str(n) in set(string_ab):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == n:
        ab.append([a, b])
contain_one = [j for i, j in ab if i == 1]
string_ab = [str(k)+str(l) for k, l in ab]

for b in contain_one:
    if str(b)+str(n) in set(string_ab):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [j for i, j in ab if i == 1]
string_ab = [str(k)+str(l) for k, l in ab]

for b in contain_one:
    if str(b)+str(n) in set(string_ab):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]
string_ab = [str(k)+str(l) for k, l in ab]

for a, b in contain_one:
    if str(b)+str(n) in set(string_ab):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]

for a, b in contain_one:
    if [b, n] in ab:
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]
contain_n = [[k, l] for k, l in ab if l == n]

for a, b in contain_one:
    second = b
    for c, d in contain_n:
        if c == second:
            print("POSSIBLE")
            exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]

for a, b in contain_one:
    second = b
    for c, d in ab:
        if c == second:
            if d == n:
                print("POSSIBLE")
                exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for g in G[N - 1]:
    if g in G[0]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
 
Matrix = []
 
for i in range (0, M):
	if P[i][0]==N:
		Matrix.append(P[i][1])
	if P[i][1]==N:
		Matrix.append(P[i][0])	
 
for i in range (0,M):
	if P[i][0]==1:
		for j in range (0, len(Matrix)):
			if Matrix[j] == P[i][1]:
				print('POSSIBLE')
				exit()
	if P[i][1]==1:
		for j in range (0, len(Matrix)):
			if Matrix[j] == P[i][0]:
				print('POSSIBLE')
				exit()
 
 
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Matrix = []

for i in range (0, M):
	if P[i][0]==N:
		Matrix.append(P[i][1])
	if P[i][1]==N:
		Matrix.append(P[i][0])	

for i in range (0,M):
	if P[i][0]==1:
		for j in range (0, len(Matrix)):
			if Matrix[j] == P[i][1]:
				print('POSSIBLE')
				exit()
	if P[i][1]==1:
		for j in range (0, len(Matrix)):
			if Matrix[j] == P[i][0]:
				print('POSSIBLE')
				exit()


print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Matrix = []

for i in range (0, M):
	if P[i][0]==N:
		Matrix.append(P[i][1])
	if P[i][1]==N:
		Matrix.append(P[i][0])	

for i in range (0,M):
	if P[i][0]==1:
		if Matrix.count(P[i][1]) > 0:
			print('POSSIBLE')
			exit()
	if P[i][1]==1:
		if Matrix.count(P[i][0]) > 0:
			print('POSSIBLE')
			exit()


print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
s = []
g = []
for _ in range(m):
  a,b = map(int, input().split())
  if a == 1: s.append(b)
  elif b == n: g.append(a)
s.sort()
g.sort()
if min(len(s), len(g)) == len(g): x,y = g,s
else: x,y = s,g
  
ok = False
for v in x:
  if v in y: 
    ok = True
    break
print("POSSIBLE" if ok else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m=MI()
lis=[LI() for i in range(m)]
pas=[]
for i in range(m):
    if lis[i][0]==1:
        pas.append(lis[i][1])
for i in range(m):
    if lis[i][1]==n:
        if lis[i][0] in pas:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
s = []
g = []
for _ in range(m):
  a,b = map(int, input().split())
  if a == 1: s.append(b)
  elif b == n: g.append(a)

ok = False
for v in s:
  if v in g: 
    ok = True
    break
print("POSSIBLE" if ok else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
ab = []
l = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        l.append(b)

for i in range(m):
    if ab[i][1] == n and ab[i][0] in l:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
cnt=0
for j in range(m):
  for k in range(m):
    if j==k:
      continue;
    else:
      a=set(lst[j])|set(lst[k])
      if len(a)==3 and 1 in a and n in a:
        cnt+=1
        break;
if cnt>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
cnt=0
for j in range(m):
  for k in range(m):
    if j==k:
      continue;
    else:
      a=set(lst[j])|set(lst[k])
      if len(a)==3 and 1 in a and n in a:
        cnt+=1
if cnt>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ans = 'IMPOSSIBLE'
abl1 = []
abl2 = []
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.append(ab)
    elif ab[1] == N:
        abl2.append(ab)
    for i in abl1:
        if [i[1], N] in abl2:
            ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
abl1 = []
abl2 = []
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.append(ab)
    elif ab[1] == N:
        abl2.append(ab)

for i in abl1:
    if [i[1], N] in abl2:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1 and [i[1],N] in abl:
        ans = 'POSSIBLE'
        print(ans)
        exit()
print(ans)

Submission status: Time Limit Exceeded

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

island = 0
ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1:
        island = i[1]
    if [island,N] in abl:
        ans = 'POSSIBLE'
        print(ans)
        exit()
print(ans)

Submission status: Time Limit Exceeded

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

island = 0
ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1:
        island = i[1]
        for v in abl:
            if v[0] == island and v[1] == N:
                ans = 'POSSIBLE'
                print(ans)
                exit()

print(ans)

Submission status: Time Limit Exceeded

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

counter = 0
island = 0
ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1:
        island = i[1]
        counter += 1
        for j in abl:
            if j[0] == island and j[1] == N:
                ans = 'POSSIBLE'
                print(ans)
                exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = list(map(int, input().split()))
    root_start = []
    root_goal = []
    for i in range(m):
        li = list(map(int, input().split()))
        if li[0] == 1:
            root_start.append(li[1])
        elif li[1] == n:
            root_goal.append(li[0])
    flg = False
    for ls in root_start:
        if ls in root_goal:
            flg = True

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
from1 = []
to_n = []
for i in range(m):
    if ab[i][0] == 1:
        from1.append(ab[i][1])
    if ab[i][1] == n:
        to_n.append(ab[i][0])

for i in range(len(from1)):
    if from1[i] in to_n:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
for o in list(set(one_li)):
    if o in list(set(to_n_li)):
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
for o in one_li:
    if o in to_n_li:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = []
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s.append(b)
    else: break
for A, B in AB:
    if B == n:
        if A in s:
            ans = "POSSIBLE"
    else: break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
s = []
g = []
for a, b in ab:
    if a == 1: s.append(b)
    elif b == n: g.append(a)
ans = "IMPOSSIBLE"
if len(s) > 0 and len(g) > 0:
    if len(s) < len(g):
        for i in range(len(s)):
            if s[i] in g: ans = "POSSIBLE"
    else:
        for i in range(len(g)):
            if g[i] in s: ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
B = []
C = []
cnt = 0
for _ in range(M):
    A.append(list(map(int, input().split())))
for i in range(M):
    if A[i][1] == N:
        B.append(i)
    if A[i][0] == 1:
        C.append(i)
for j in B:
    for k in C:
        if A[j][0] == A[k][1]: cnt += 1
print("POSSIBLE" if cnt != 0 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
cnt = 0
for _ in range(M):
    A.append(list(map(int, input().split())))
for i in range(M):
    for j in range(M):
        if A[i][0] == 1 and A[j][1] == N and A[j][0] == A[i][1]:
            cnt += 1
print("POSSIBLE" if cnt != 0 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s.append(y)
    elif y == n:
        e.append(x)
s.sort()
e.sort()
flag = False
for i in s:
    for j in e:
        if i < j:
            break
        if i == j:
            flag = True
            break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s.append(y)
    elif y == n:
        e.append(x)
flag = False
for i in s:
    for j in e:
        if i == j:
            flag = True
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")