2603. [HZOI 2016]颓废元

【题目描述】

JJ博士最近发现，人们寒假颓废与一种名字叫做“颓废元”的化学物质有关。这种化学物质作用于人的脑子中，通过人的神经网络到达人的大脑。

JJ博士开始尝试利用手术解决颓废问题，而解决方案就是切除有关神经。

当然了，由于有关神经都在人脑中，所以要尽量选择伤害最小的方式来切除，否则做完手术之后你可能会“脑子里少根弦”。

为了完成这一计划，JJ博士需要你的帮助。

作为博士的8号助手，你平时很少有机会能展示自我（活都被前7号抢了），所以你要抓住机会，展现自我。

【输入格式】

一个整数n，表示有n个突触（你可以理解为多条神经元供用一个突触），其中1号为“颓废元”产生的地方，n号为“颓废元”作用的地方。

一个整数m，表示共有m个神经元。

接下来m行，每行两个1到n的整数x,y,z，表示x到y有一个神经元，最多能传载z单位的“颓废元”。

接下来一个整数T，表示将会有T组询问。

每行两个整数ope 和 x，

若ope==1，则询问切掉第x个神经元能存在于一种最小代价切割方案中。

若ope==2，则询问若要以最小代价阻断“颓废元”的传播，第x个神经元是否一定要切除。

最后，虽然JJ博士没有询问，但是你为了说明自己很优秀，表现自己的能力很强，你需要告诉他若不切除，到达大脑的“颓废元”数目是多少。

同时，你还要告诉JJ博士一种最小代价的切除方案。

什么是最小代价呢？显然切除较细的（传载“颓废元”数目较小的）的代价比切除较粗的代价小，在很多种方案代价相同时，选择字典序最小的方案。

【输出格式】

T行，每行对应一个答案1或者0。

1行，表示若不切除，到达大脑的“颓废元”数目是多少

1行，表示最小代价的切除方案，每个数之间用一个空格隔开。

【样例输入】

7



7



1 2 10



2 3 1



3 4 1



4 7 10



1 5 10



5 6 1



6 7 10



5



1 2



1 3



1 6



2 6



2 2

【样例输出】

1



1



1



1



0



2



2 6

【提示】

对于24%的数据，n<=20,m<=400,T<=2

对于60%的数据，50%左右的神经元的z等于1

对于100%的数据，n<=400,m<=4000,T<=8000，0<z<=m

【来源】

一只名字很长的蒟蒻