# NmapPort

* Input: NP.inp
* Output: NP.out

Nmap là một công cụ miễn phí với mã nguồn mở, công cụ này dùng để quét các cổng đang mở của một server. Gần đầy sau khi học cách sử dụng Nmap và nhận ra được sự hạn chế, An đã quyết định cải tiến tốc độ chạy của công cụ này bằng một thuật toán nào đó. Vì mới học làm hacker được 1 tháng nên hiểu biết về cách cổng của An rất hạn chế, cụ thế An được biết như sau:

* $1$ $u$ $v$ :Nếu biết được thông tin về cổng $u$ chắc chắn sẽ biết được thông tin cổng $v$.
* $2$ $u$ $l$ $r$ :Nếu biết được thông tin cổng $u$ thì chắc chắn biết được thông tin từ công $l$ đến cổng $r$.
* $3$ $l$ $r$ $v$ :Nếu biết được thông tin của 1 trong số các cổng từ $l \rightarrow r$ thì sẽ biết được thông tin của cổng $v$.

Hiện tại An đã hack được cổng s và muốn biết số lần lấy thông tin tối thiểu để có thể biết được thông tin của bất kì cổng nào.

Dữ liệu đầu vào: dòng đầu tiên bao gồm $n$,$m$,$s$(số cổng cần biết, số hiểu biết về các cổng của An, cổng mà An được biết trước). $m$ dòng tiếp theo sẽ bao gồm $t$ (loại thông tin mà An biết). Nếu $t$ = 1 thì sẽ đi kèm theo 2 số $u$ $v$ miểu tả thông tin số 1. Nếu $t$ = 2 hoặc 3 thì sẽ kèm theo 3 số $u$,$v$,$k$ miêu tả thông tin số 2 hoặc số 3.

Dữ liệu đầu ra: in ra 1 dòng gồm $n$ số nguyên. Số nguyên thứ $i$ cho biết số thông tin tối thiểu cần thu thập để biết được thông tin của cổng $i$, nếu không có cách nào thu thập được thông tin cổng $i$ thì xuất ra $-1$.

Trong tất cả các subtask thì $s,u,v <= n, t <= 3$.

Subtask1: $n <= 1e5, m <= 5e5$, $t = 1$ (20% số điểm)
Subtask2: $n <= 1000,m<= 3000$ (20% số điểm)
Subtask3: $n <= 1e5 ,m<= 5e5$, $t <= 2$ (30% số điểm)
Subtask4: $n <= 1e5 ,m <= 5e5$ ,$t<=3$ (30% số điểm)