小针是 C 市的中考状元,他的父亲网友是C市市长。
C 市正在修路,C市共有 2n 个居民点,m 条道路,每条道路连接两个居民点 u 和 v,满足 1≤u≤n, n+1≤v≤2n。现在 C 市需要选择一些道路进行维修,进行维修的道路不能通行。C 市的市民认为,如果某个居民点不能通过可以通行的道路走到其他点,那么生活在这个居民点是非常无趣的,他们就会在网上狂喷网友从而让网友的儿子小针很没面子。C 市的市民还认为,如果修路开始后和某个居民点与大于 k 条没有被维修的道路直接相连,那么这个居民点就会变得过于吵闹,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。此外,如果某个居民点的市民从自己家开始,经过不重复的道路后回到了自己原来的居民点,这些市民就会很迷茫,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。为了方便管理市民,网友希望把市民分成尽量多的组,使得组与组之间的市民不能通过可以通行的道路到达。
小针发现,每条路的风景都是不一样的,第 i 条路的风景可以用一个正整数 wi 描述。由于小针有私人飞机,他可以无视道路直接到达某个顶点,但是一条路正在维修,小针就无法在这条路上赏风景。他希望没有被维修的道路的总风景值最大。当然,他不能违抗他爸爸的意愿,他也不想没面子。现在小针找到你,希望你能帮他计算一下,没被维修的道路的总风景值最大能达到多少。
输入格式
第一行三个正整数 n,m,k。
以下 m 行每行三个正整数 ui,vi,wi,保证 1≤ui≤n,n+1≤vi≤2n 表示一条边连接第 ui 个和第 vi 个居民点,风景值为 wi。
输入数据保证任意两个居民点之间至多只有一条道路。
输出格式
一行两个正整数,表示维修的道路数量和最大总风景值。
如果无论选择修哪些道路,小针都很没面子,输出"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≤10,m≤20
Subtask2 [30pts]: k=2
Subtask3 [30pts]: k=n
Subtask4 [32pts]: 无特殊条件
在以上所有subtask中,1≤k≤n≤100,1≤m≤2000,0≤w≤10000.