QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Hackable ✓
Statistics

小针是 C 市的中考状元,他的父亲网友是C市市长。

C 市正在修路,C市共有 $2n$ 个居民点,$m$ 条道路,每条道路连接两个居民点 $u$ 和 $v$,满足 $1\le u\le n$, $n+1\le v\le 2n$。现在 C 市需要选择一些道路进行维修,进行维修的道路不能通行。C 市的市民认为,如果某个居民点不能通过可以通行的道路走到其他点,那么生活在这个居民点是非常无趣的,他们就会在网上狂喷网友从而让网友的儿子小针很没面子。C 市的市民还认为,如果修路开始后和某个居民点与大于 $k$ 条没有被维修的道路直接相连,那么这个居民点就会变得过于吵闹,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。此外,如果某个居民点的市民从自己家开始,经过不重复的道路后回到了自己原来的居民点,这些市民就会很迷茫,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。为了方便管理市民,网友希望把市民分成尽量多的组,使得组与组之间的市民不能通过可以通行的道路到达

小针发现,每条路的风景都是不一样的,第 $i$ 条路的风景可以用一个正整数 $w_i$ 描述。由于小针有私人飞机,他可以无视道路直接到达某个顶点,但是一条路正在维修,小针就无法在这条路上赏风景。他希望没有被维修的道路的总风景值最大。当然,他不能违抗他爸爸的意愿,他也不想没面子。现在小针找到你,希望你能帮他计算一下,没被维修的道路的总风景值最大能达到多少。

输入格式

第一行三个正整数 $n$,$m$,$k$。

以下 $m$ 行每行三个正整数 $u_i,v_i,w_i$,保证 $1\le u_i\le n,n+1\le v_i\le 2n$ 表示一条边连接第 $u_i$ 个和第 $v_i$ 个居民点,风景值为 $w_i$。

输入数据保证任意两个居民点之间至多只有一条道路。

输出格式

一行两个正整数,表示维修的道路数量和最大总风景值。

如果无论选择修哪些道路,小针都很没面子,输出"FACELESS"(不含引号)

样例数据

样例 1 输入

3 5 2
1 4 1
1 5 2
1 6 3
2 4 4
2 5 5

样例 1 输出

FACELESS

样例 2 输入

3 4 2
1 4 1
2 4 2
3 5 3
3 6 4

样例 2 输出

0 10

子任务

评测采用子任务制,为了拿到某个子任务的分数,必须通过这个子任务的所有数据。

Subtask1 [8pts]: $n\le10$,$m\le 20$

Subtask2 [30pts]: $k=2$

Subtask3 [30pts]: $k=n$

Subtask4 [32pts]: 无特殊条件

在以上所有subtask中,$1\le k\le n\le 100$,$1\le m\le 2000$,$0\le w\le 10000$.