Problem:


Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq 2×10^5

1 \leq p_i \leq N (1 \leq i \leq M)

1 \leq q_i \leq N (1 \leq i \leq M)

1 \leq c_i \leq 10^6 (1 \leq i \leq M)

p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:

N M
p_1 q_1 c_1
:
p_M q_M c_M

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N,M=map(int,input().split())
mod =10**9
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    table[a].add((a+c*mod,1))
    table[b].add((b+c*mod,1))
    table[a+c*mod].add((a,0))
    table[b+c*mod].add((b,0))
    table[a+c*mod].add((b+c*mod,0))
    table[b+c*mod].add((a+c*mod,0))
    visit[a]=0
    visit[b]=0
    visit[b+c*mod]=0
    visit[a+c*mod]=0
#print(table)

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    x,cost=H.popleft()
    if x==N:
        ans=cost
        break
    for y,c in table[x]:
        if visit[y]==1:
            continue
        visit[y]=1
        if c==1:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    p,q,c=map(int,input().split())
    p,q=p-1,q-1
    table[p].append((q,c,i))
    table[q].append((p,c,i))
visit=[False]*M
H=deque()
#visit[0]=True
arcost=[10**9+7]*N
arcost[0]=0
for x,c,i in table[0]:
    H.append((x,c,1))
    arcost[x]=1
    #visit[x]=True
    visit[i]=True
#print(H)
#print(table)
while H:
    pt,ro,cost=H.popleft()
    #print(H)
    arcost[pt]=min(arcost[pt],cost)
    for npt,nro,i in table[pt]:
        if visit[i]:
            continue
        if ro==nro:
            H.appendleft((npt,nro,cost))
            visit[i]=True
        elif ro!=nro:
            H.append((npt,nro,cost+1))
            visit[i]=True
#print(arcost)
#print(visit)
if arcost[N-1]==10**9+7:
    print(-1)
else:
    print(arcost[N-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

es = [[] for i in range(N)]
for i in range(M):
    p,q,c = map(lambda x:int(x)-1, input().split())
    es[p].append((q,c))
    es[q].append((p,c))

INF = N*999
costs = [INF] * N
costs[0] = 0
visited_by = [set() for i in range(N)]
q = deque([(0,-1)])
while q:
    v,c1 = q.popleft()
    for to,c2 in es[v]:
        if c2 in visited_by[to]: continue
        visited_by[to].add(c2)
        trans = int(c1 != c2)
        newcost = costs[v] + trans
        if newcost > costs[to]: continue
        if to == N-1:
            print(newcost)
            exit()
        costs[to] = newcost
        if trans:
            q.append((to,c2))
        else:
            q.appendleft((to,c2))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

es = [[] for i in range(N)]
for i in range(M):
    p,q,c = map(lambda x:int(x)-1, input().split())
    es[p].append((q,c))
    es[q].append((p,c))

INF = N*999
costs = [INF] * N
costs[0] = 0
q = deque([(0,-1)])
while q:
    v,c1 = q.popleft()
    for to,c2 in es[v]:
        trans = int(c1 != c2)
        newcost = costs[v] + trans
        if newcost >= costs[to]: continue
        if to == N-1:
            print(newcost)
            exit()
        costs[to] = newcost
        if trans:
            q.append((to,c2))
        else:
            q.appendleft((to,c2))
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
Rails = [[] for _ in range(N)]
Costs = {(i, -1): 1000000000 for i in range(N)}
Visited = {(i, -1): False for i in range(N)}
for _ in range(M):
    p, q, c = map(int, input().split())
    Rails[p-1].append((q-1, c))
    Rails[q-1].append((p-1, c))
    Costs[(p-1, c)] = 1000000000
    Costs[(q-1, c)] = 1000000000
    Visited[(p-1, c)] = False
    Visited[(q-1, c)] = False

Q = [(0, 0, -1)]
heapq.heapify(Q)
while Q:
    currentCost, currentNode, currentCompany = heapq.heappop(Q)
    if not Visited[(currentNode, currentCompany)]:
        Visited[(currentNode, currentCompany)] = True
        if currentCompany == -1:
            for nextNode, nextCompany in Rails[currentNode]:
                if not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost + 1:
                        Costs[(nextNode, nextCompany)] = currentCost + 1
                        heapq.heappush(Q, (currentCost + 1, nextNode, nextCompany))
        else:
            if not Visited[(currentNode, -1)]:
                if Costs[(currentNode, -1)] > currentCost:
                    Costs[(currentNode, -1)] = currentCost
                    heapq.heappush(Q, (currentCost, currentNode, -1))
            for nextNode, nextCompany in Rails[currentNode]:
                if nextCompany == currentCompany and not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentNode:
                        Costs[(nextNode, nextCompany)] = currentNode
                        heapq.heappush(Q, (currentCost, nextNode, nextCompany))
minCost = Costs[(N-1, -1)]
print(minCost if minCost < 1000000000 else -1)

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
Rails = [[] for _ in range(N)]
for _ in range(M):
    p, q, c = map(int, input().split())
    Rails[p-1].append((q-1, c))
    Rails[q-1].append((p-1, c))
Cost = [1000000000] * N
Visited = [False] * N
Cost[0] = 0
Q = [(0, 0, 1000000)]
heapq.heapify(Q)

while Q:
    currentCost, currentNode, currentCompany = heapq.heappop(Q)
    if not Visited[currentNode]:
        Visited[currentNode] = True
        for nextNode, nextCompany in Rails[currentNode]:
            if not Visited[nextNode]:
                addcost = (0 if currentCompany == nextCompany else 1)
                if Cost[nextNode] > currentCost + addcost:
                    heapq.heappush(Q, (currentCost + addcost, nextNode, nextCompany))
                    Cost[nextNode] = currentCost + addcost

print(Cost[N-1] if Cost[N-1] < 1000000000 else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(a-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    visited[(a,c)]=True
    for i in G0[(a,c)]:
      if not visited[i]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i]:
        stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(a-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    if not visited[(stack[0][0],stack[0][1])]:
      a,c,m=stack.popleft()
      if a==N-1 and c==-1:
        return m
      visited[(a,c)]=True
      for i in G0[(a,c)]:
        if not visited[i]:
          stack.appendleft((i[0],i[1],m))
      for i in G1[(a,c)]:
        if not visited[i]:
          stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

ans = 0
L = {1}
L2 = set()
C = set()

def dfs(source, company, res):
    for d, c in E[source].items():
        if d in res:
            continue
        if d in C:
            continue
        if company == c:
            res.add(d)
            res |= dfs(d, c, res)
    return res


while len(L) != 0:
    ans += 1
    C |= L
    for source in L:
        for destination, company in E[source].items():
            L2 |= dfs(destination, company, {destination}) - {source}
    if N in L2:
        break
    L = L2
    L2 = set()
else:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

ans = 0
L = {1}
L2 = set()
C = set()

def dfs(source, company, res):
    for d, c in E[source].items():
        if d in res:
            continue
        if d in C:
            continue
        if company == c:
            res.add(d)
            res |= dfs(d, c, res)
    return res


while len(L) != 0:
    ans += 1
    C |= L
    for source in L:
        for destination, company in E[source].items():
            L2 |= dfs(destination, company, {destination}) - {destination}
    if N in L2:
        break
    L = L2
    L2 = set()
else:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

ans = 0
L = {1}
L2 = set()
C = set()

def dfs(source, company, res):
    for d, c in E[source].items():
        if d in res:
            continue
        if d in C:
            continue
        if company == c:
            res.add(d)
            res |= dfs(d, c, res)
    return res


while len(L) != 0:
    ans += 1

    for source in L:
        for destination, company in E[source].items():
            L2 |= dfs(destination, company, {destination}) - {destination}
    if N in L2:
        break
    C |= L
    L = L2
    L2 = set()
else:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

dist = defaultdict(lambda: float("inf"))  # 始点から各頂点までの最短距離を格納する
dist[(1, 0)] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, (1, 0)))  # 始点をpush
ans = float("inf")

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    if src[0]==N:
        ans = min(ans, prov_cost)

    # 他の頂点の探索
    for dest, company in E[src[0]].items():
        cost = 0 if src[1]==company else 1
        if dist[(dest, company)] > dist[src] + cost:
            new_dist = dist[src] + cost
            dist[(dest, company)] = new_dist  # distの更新
            heapq.heappush(q, (new_dist, (dest, company)))  # キューに新たな仮の距離の情報をpush

print(ans if ans!=float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

dist = defaultdict(lambda: float("inf"))  # 始点から各頂点までの最短距離を格納する
prev = defaultdict(lambda: float("inf"))  # 最短経路における，その頂点の前の頂点のIDを格納する

dist[(1, 0)] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, (1, 0)))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    for dest, company in E[src[0]].items():
        cost = 0 if src[1]==company else 1
        if dist[(dest, company)] > dist[src] + cost:
            dist[(dest, company)] = dist[src] + cost  # distの更新
            heapq.heappush(q, (dist[(dest, company)], (dest, company)))  # キューに新たな仮の距離の情報をpush
            prev[(dest, company)] = src  # 前の頂点を記録

ans = float("inf")
for v, d in dist.items():
    if v[0]==N:
        ans = min(ans, d)

print(ans if ans!=float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
E = defaultdict(lambda: defaultdict(lambda: float("inf")))

for i in range(M):
    p, q, c = map(int, input().split())
    E[p][q] = c
    E[q][p] = c

dist = defaultdict(lambda: float("inf"))  # 始点から各頂点までの最短距離を格納する
prev = defaultdict(lambda: float("inf"))  # 最短経路における，その頂点の前の頂点のIDを格納する

dist[(1, 0)] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, (1, 0)))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    for dest, company in E[src[0]].items():
        cost = 0 if src[1]==company else 1
        if dist[(dest, company)] > dist[src] + cost:
            dist[(dest, company)] = dist[src] + cost  # distの更新
            heapq.heappush(q, (dist[(dest, company)], (dest, company)))  # キューに新たな仮の距離の情報をpush
            prev[(dest, company)] = src  # 前の頂点を記録

ans = float("inf")
for v, d in dist.items():
    if v[0]==N:
        ans = min(ans, d)

print(ans if ans!=float("inf") else -1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def bfs01(g, s):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    if s not in d:
        return d
    q = deque()
    q.append((d[s], s))

    while q:
        c, u = q.popleft()
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                if g[u][v] == 0:
                    q.appendleft((d[v], v))
                else:
                    q.append((d[v], v))
    return d


@mt
def slv(N, M):

    g = defaultdict(dict)
    NM = 30
    for _ in range(M):
        p, q, c = input().split()
        p = int(p)
        q = int(q)
        c = int(c)

        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp][cq] = 0
        g[cq][cp] = 0
        g[cp][p] = 0
        g[cq][q] = 0
        g[p][cp] = 1
        g[q][cq] = 1

    d = bfs01(g, 1)
    return -1 if N not in d else d[N]


def main():
    N, M = read_int_n()

    print(slv(N, M))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = sys.maxsize

    if s not in d:
        return d
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, M, PQC):

    g = defaultdict(dict)
    for p, q, c in PQC:
        g[(c, p)][(c, q)] = 0
        g[(c, q)][(c, q)] = 0
        g[(c, p)][(p, )] = 0
        g[(c, q)][(q, )] = 0
        g[(p, )][(c, p)] = 1
        g[(q, )][(c, q)] = 1

    d = Dijkstra(g, (1,))
    return -1 if (N, ) not in d else d[(N, )]


def main():
    N, M = read_int_n()
    PQC = [read_int_n() for _ in range(M)]
    print(slv(N, M, PQC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
D = {}
Edges = []


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    Edges.append((p, q))

    if (p, c) in D:
        UF.union(D[p, c], i)
    D[p, c] = i

    if (q, c) in D:
        UF.union(D[q, c], i)
    D[q, c] = i

UF.all_find()

Firm_Node = defaultdict(set)
for i in range(M):
    p, q = Edges[i]
    Firm_Node[UF.par[i]].add(p)
    Firm_Node[UF.par[i]].add(q)

G = defaultdict(list)
for firm, node in Firm_Node.items():
    for n in node:
        G[n].append(firm + N)
        G[firm + N].append(n)


def dijkstra(x):
    d = {x: 0, N-1: 10**9}
    visited = {x}

    # d, u
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[1]
        visited.add(u)

        for node in G[u]:
            d.setdefault(node, float('inf'))
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                if d[N-1] < 10**9:
                    return d
                queue.appendleft([d[u]+1, node])
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] < M else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
D = {}
Edges = []


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    Edges.append((p, q))

    if (p, c) in D:
        UF.union(D[p, c], i)
    D[p, c] = i

    if (q, c) in D:
        UF.union(D[q, c], i)
    D[q, c] = i

UF.all_find()

Firm_Node = defaultdict(set)
for i in range(M):
    p, q = Edges[i]
    Firm_Node[UF.par[i]].add(p)
    Firm_Node[UF.par[i]].add(q)

G = defaultdict(list)
for firm, node in Firm_Node.items():
    for n in node:
        G[n].append(firm + N)
        G[firm + N].append(n)


def dijkstra(x):
    d = {x: 0, N-1: 10**9}
    visited = {x}

    # d, u
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[1]
        visited.add(u)

        for node in G[u]:
            d.setdefault(node, float('inf'))
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                queue.appendleft([d[u]+1, node])
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] not in [0, float('inf')] else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
D = {}
Edges = []


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    Edges.append((p, q))

    if (p, c) in D:
        UF.union(D[p, c], i)
    D[p, c] = i

    if (q, c) in D:
        UF.union(D[q, c], i)
    D[q, c] = i

UF.all_find()

Firm_Node = defaultdict(set)
for i in range(M):
    p, q = Edges[i]
    Firm_Node[UF.par[i]].add(p)
    Firm_Node[UF.par[i]].add(q)

G = defaultdict(list)
for firm, node in Firm_Node.items():
    for n in node:
        G[n].append(firm + N)
        G[firm + N].append(n)


def dijkstra(x):
    d = {x: 0, N-1: 10**9}
    visited = {x}

    # d, u
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[1]
        visited.add(u)

        for node in G[u]:
            d.setdefault(node, float('inf'))
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                if d[N-1] < 10**9:
                    return d
                queue.appendleft([d[u]+1, node])
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] not in [0, float('inf')] else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
D = {}
E = []
roads = defaultdict(set)


for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    E.append((p, q))

    if (p, c) in D:
        UF.union(D[(p, c)], i)
    D[(p, c)] = i
    if (q, c) in D:
        UF.union(D[q, c], i)
    D[(q, c)] = i

# UFの親番号をきれいな並び順にする
par_dict = {n: i for i, n in enumerate(sorted(list(set(UF.par))))}
for i in range(M):
    UF.par[i] = par_dict[UF.par[i]]
par_dict = None

# 連結した道番号: そこに属している道の辞書をつくる
for i in range(M):
    roads[UF.par[i] + N].add(E[i])
E = None

# 属している道->頂点にばらす
for key, edge in roads.items():
    node = set()
    for p, q in edge:
        node.add(p)
        node.add(q)
    roads[key] = node

# 二部グラフ : N番目からが連結した道
if roads.keys():
    G_node_num = max(roads.keys()) + 1
else:
    G_node_num = 1

G = [[] for _ in range(G_node_num)]
for key, nodes in roads.items():
    for node in nodes:
        G[node].append([key, 1])
        G[key].append([node, 1])


def dijkstra(x):
    d = [float('inf')] * G_node_num
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] != float('inf') else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
D = {}
E = []
roads = defaultdict(set)


for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    E.append((p, q))

    if (p, c) in D:
        UF.union(D[(p, c)], i)
    D[(p, c)] = i
    if (q, c) in D:
        UF.union(D[q, c], i)
    D[(q, c)] = i

# UFの親番号をきれいな並び順にする
par_dict = {n: i for i, n in enumerate(sorted(list(set(UF.par))))}
for i in range(M):
    UF.par[i] = par_dict[UF.par[i]]
par_dict = None

# 連結した道番号: そこに属している道の辞書をつくる
for i in range(M):
    roads[UF.par[i] + N].add(E[i])
E = None

# 属している道->頂点にばらす
for key, edge in roads.items():
    node = set()
    for p, q in edge:
        node.add(p)
        node.add(q)
    roads[key] = node

# 二部グラフ : N番目からが連結した道
if roads.keys():
    G_node_num = max(roads.keys()) + 1
else:
    G_node_num = 1

G = [[] for _ in range(G_node_num)]
for key, nodes in roads.items():
    for node in nodes:
        G[node].append([key, 1])
        G[key].append([node, 1])


def dijkstra(x):
    d = [float('inf')] * G_node_num
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d

dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] != float('inf') else -1)