연결성

바이토티아에는 $n$개의 도시가 있다. 현재 이 나라에는 고속도로가 없다. 하지만 바이토티아 정부는 앞으로 $m$개의 고속도로로 이루어진 네트워크를 순차적으로 건설할 계획을 세웠다. 계획된 고속도로는 모두 양방향이며, $1$부터 $d$까지 번호가 붙은 $d$가지 종류 중 하나이다.

미래의 어떤 시점을 고정하자. 순서쌍 $(a,b)$가 잘 연결되어 있다고 말할 수 있는 것은 $a=b$이거나, 모든 종류 $t=1,\ldots,d$에 대해 $t$종류의 고속도로만 이용해 $a$에서 $b$로 이동할 수 있을 때이다.

계획된 고속도로가 건설되는 순서가 주어진다. $k=1,\ldots,m$ 각각에 대해, 처음 $k$개의 고속도로가 건설된 후 잘 연결된 도시 순서쌍의 개수를 구하라.

입력의 첫 줄에는 세 정수 $d$, $n$, $m$이 주어진다 ($1 \le d \le 200$, $1 \le n \le 5000$, $1 \le m \le 1\,000\,000$). 이는 각각 고속도로의 종류 수, 도시의 수, 계획된 고속도로의 수이다. 도시는 $1$부터 $n$까지 번호가 붙어 있다. 다음 $m$개의 줄은 계획된 고속도로를 나타낸다. 이 중 $i$번째 줄에는 세 정수 $a\_i$, $b\_i$, $k\_i$가 주어진다 ($1 \le a\_i,b\_i \le n$, $a\_i \neq b\_i$, $1 \le k\_i \le d$). 이는 $i$번째 고속도로가 $a\_i$와 $b\_i$를 잇고 종류가 $k\_i$임을 뜻한다.

정확히 $m$개의 줄을 출력한다. 이 중 $k$번째 줄에는 처음 $k$개의 고속도로가 건설된 후 잘 연결된 도시 순서쌍의 개수를 나타내는 정수 하나를 출력한다.