[NOI2007]追捕盗贼

成绩 开启时间 2014年09月19日 星期五 10:03
折扣 0.8 折扣时间 2014年09月26日 星期五 10:03
允许迟交 关闭时间 2014年09月26日 星期五 10:03
输入文件 catch.in 输出文件 catch.out

追捕盗贼

【任务描述】


魔法国度Magic Land里最近出现了一个大盗Frank,他在Magic Land四处作案,专门窃取政府机关的机密文件(因而有人怀疑Frank是敌国派来的间谍)。
为了捉住Frank,Magic Land的安全局重拳出击!
Magic Land由N个城市组成,并且这N个城市又由恰好N-1条公路彼此连接起来,使得任意两个城市间都可以通过若干条公路互达。从数据结构的角度我们也可以说,这N个城市和N-1条公路形成了一棵树。
例如,下图就是Magic Land的一个可能格局(4个城市用数字编号,3条公路用字母编号):

大盗Frank能够在公路上以任意速度移动。
比方说,对于上图给出的格局,在0.00001秒钟内(或者任意短的一段时间内),Frank就可以从城市1经过城市2到达城市4,中间经过了两条公路。
想要生擒Frank困难重重,所以安全局派出了经验丰富的警探,这些警探具有非凡的追捕才能:
1. 只要有警探和Frank同处一个城市,那么就能够立刻察觉到Frank,并且将其逮捕。
2. 虽然Frank可以在公路上以任意快的速度移动,但是如果有警探和Frank在同一条公路上相遇,那么警探也可以立刻察觉到Frank并将其逮捕。
安全局完全不知道Frank躲在哪个城市,或者正在哪条公路上移动,所以需要制定一个周密的抓捕计划,计划由若干步骤组成。在每一步中,可以做如下几件事中的一个:
1. 在某个城市空降一位警探。警探可以直接从指挥部空降到Magic Land的任意一个城市里。此操作记为“L x”,表示在编号为x的城市里空降一位警探。耗时1秒。
2. 把留在某个城市里的一位警探直接召回指挥部。以备在以后的步骤中再度空降到某个城市里。此操作记为“B x”。表示把编号为x的城市里的一位警探召回指挥部。耗时1秒。
3. 让待在城市x的一位警探沿着公路移动到城市y,此操作记为“M x y”。耗时1秒。当然,前提是城市x和城市y之间有公路。如果在警探移动的过程中,大盗Frank也在同一条公路上,那么警探就抓捕到了Frank。
现在,由你来制定一套追捕计划,也就是给出若干个步骤,需要保证:无论大盗Frank一开始躲在哪儿,也无论Frank在整个过程中如何狡猾地移动 (Frank大盗可能会窃取到追捕行动的计划书,所以他一定会想尽办法逃避),他一定会被缉拿归案。
希望参与的警探越少越好,因为经验丰富的警探毕竟不多。
例如对于前面所给的那个图示格局,一个可行的计划如下:
1. L 2 在城市2空降一位警探。注意这一步完成之后,城市2里不会有Frank,否则他将被捉住。
2. L 2 再在城市2空降一位警探。
3. M 2 1 让城市2的一位警探移动到城市1。注意城市2里还留有另一位警探。这一步完成之后,城市1里不会有Frank,公路A上也
不会有Frank。也就是说,假如Frank还没有被逮捕,那么他只能是在城市3或城市4里,或者公路B或公路C上。
4. B 1 召回城市1的一位警探。注意虽然召回了这位警探,但是由于我们始终留了一位警探在城市2把守,所以Frank仍然不可能跑到
城市1或者是公路A上。
5. L 3 在城市3空降一位警探。注意这一步可以空降在此之前被召回的那位警探。这一步完成之后,城市3里不会有Frank,否则他会被捉住。
6. M 3 2 让城市3里的一位警探移动到城市2。这一步完成之后,如果Frank还没有被捉住,那他只能是在公路C上或者城市4里。注意
这一步之后,城市2里有两位警探。
7. M 2 4 让城市2里的一位警探移动到城市4。这一步完成之后,Frank一定会被捉住,除非他根本就没来Magic Land。
这个计划总共需要2位警探的参与。可以证明:如果自始至终只有1名或者更少的警探参与,则Frank就会逍遥法外。
你的任务很简单:对于一个输入的Magic Land的格局,计算S,也就是为了追捕Frank至少需要投入多少位警探,并且给出相应的追捕计划步骤。

【输入格式】
输入文件给出了Magic Land的格局。
第一行一个整数N,代表有N个城市,城市的编号是1~N。
接下来N-1行,每行有两个用空格分开的整数xi,yi,代表城市xi,yi之间有公路相连。保证1≤xi,yi≤N

【输出格式】

向输出文件输出你所给出的追捕计划。
第一行请输出一个整数S,代表追捕计划需要多少位警探。
第二行请输出一个整数T,代表追捕计划总共有多少步。
接下来请输出T行,依次描述了追捕计划的每一步。每行必须是以下三种形式之一:
z“L x”,其中L是大写字母,接着是一个空格,再接着是整数x,代表在城市x空降一位警探。你必须保证1≤x≤N。
z“B x”,其中B是大写字母,接着是一个空格,再接着是整数x,代表召回城市x的一位警探。你必须保证1≤x≤N,且你的计
划执行到这一步之前,城市x里面确实至少有一位警探。
z“M x y”,其中M是大写字母,接着是一个空格,再接着是整数x,再跟一个空格,最后一个是整数y。代表让城市x的一位警
探沿着公路移动到城市y。你必须保证1≤x, y≤N,且你的计划执行到这一步之前,城市x里面确实至少有一位警探,且城市x, y之前
确实有公路。
必须保证输出的S确实等于追捕计划中所需要的警探数目。

【输入样例】

4
1 2
3 2
2 4

【输出样例】

2
7
L 2
L 2
M 2 1
B 1
L 3
M 3 2
M 2 4

【评分方法】

对于任何一个测试点:
如果输出的追捕计划不合法,或者整个追捕计划的步骤数T超过了20000,或者追捕计划结束之后,不能保证捉住Frank,则不能得分。

否则,用你输出的S和我们已知的标准答案S *相比较:
1. 若S 2. 若S=S *,则得到100%的分。
3. 若S * 4. 若S * +2 5. 若S * +4 6. 若S>S * +8,则得到10%的分。

【数据规模】

输入保证描述了一棵连通的N结点树,1≤N≤1 000。