TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

97.2% (35/36)

Submission's AC Ratio

51.0% (51/100)

Description

你,もも,逃出了棋盤格,朝著他的目標向前邁進,接下來的故事請自行想像,現在你在考建中資訊校內賽。
給你一張$n$個點$m$條邊的無向簡單圖$G$,每條邊的邊權非$0$即$1$。
再給你一個正整數$k$,問$G$是否存在一個生成樹其邊權總合為$k$。

Input Format

第一行有3個正整數$n, m, k$,分別代表$G$的點數、邊數以及題目要問的那個$k$。
接下來有$ m$行,每一行包含三個整數$u, v, c$,代表$G$裡存在一條邊權為$c$從$u$連到$v$的邊。

子題1滿足 : 若權重為$k$的生成樹存在,則不存在任何權重比$k$小的生成樹
子題2滿足 : 若權重為$k$的生成樹存在,則不存在任何權重比$k$大的生成樹

所有子題滿足:
$2 \leq n \leq 100000$
$2 \leq m \leq 300000$
$0 \leq k \leq n-1$
$1 \leq u, v \leq n$
$c \in {0, 1}$

Output Format

如果存在要求的生成樹,輸出"TAK"(不含引號),不然則輸出"NIE"(不含引號)。

Sample Input

#1:
3 3 1
1 2 1
2 3 0
1 3 0

#2:
4 3 2
1 2 1
2 3 1
3 4 1

Sample Output

#1:
TAK

#2:
NIE

Hints

我們說$T$是$G$的生成樹若且唯若:
1.$T$是一棵樹
2.$V(G) = V(T)$
3.$\forall e(u, v) \in T, e(u, v) \in G$

where $V(G)$代表$G$的點集合,$e(u, v)$代表一條連接點$u$跟$v$的邊

Problem Source

Subtasks

For Testdata: 0 ~ 3, Score: 10
For Testdata: 4 ~ 8, Score: 20
For Testdata: 9 ~ 14, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 3000 131072 65536
2 3000 131072 65536
3 3000 131072 65536
4 5000 131072 65536
5 5000 131072 65536
6 5000 131072 65536
7 5000 131072 65536
8 5000 131072 65536
9 5000 131072 65536
10 5000 131072 65536
11 5000 131072 65536
12 5000 131072 65536
13 5000 131072 65536
14 5000 131072 65536