### 问题描述 P 哥哥发明了一台堆栈机。这台堆栈机遵循“后进先出”的原则，它有无限大的空间，可以存储无限多的物品。 P 哥哥决定把这台堆栈机装到卡车上，然后用这台卡车来运输货物。P 哥哥所在的城市有很多单向的道路，然后同时也有很多交叉路口。沿着每条路，都有需要拉走和卸载的货物。注意，如果某条道路需要某件货物，卡车如果途径这条道路就必须提供这件货物。而且由于卡车中货物不能交换顺序，提供这件货物时必须保证这件货物位于栈顶的位置。你的任务是规划卡车的路线，使得卡车在路线的开始和结束时都是空的。 ### 输入描述 输入第一行包含一个整数 $t$ ，表示测试用例的数量。 对于每个测试用例： 第一行包含三个整数 $n,m,q$ ，分别表示城市中的交叉口和道路的数量以及查询的数量。交叉口从 $1$ 到 $n$ 编号。 接下来输入 $m$ 行，每一行包含 $x,y,z$ 三个整数。表示从交叉口 $x$ 到交叉口 $y$ 存在一条道路，当卡车经过这条道路，如果 $z$ 是一个正数，就说明需要拉走一件重为 $z$ 的货物；如果 $z$ 为负数，就说明需要卸下一件重为 $-z$ 的货物。 接下来输入 $q$ 行，每行描述一个查询，包括两个整数，即卡车开始和结束的交叉口。 数据保证： $1 \leq t \leq 10,1 \leq n \leq 100,1 \leq m,q \leq 10^5，40 \leq |z| \leq 220$ 。 ### 输出描述 对于每个查询，输出一行，包含一个整数，给出卡车从路线开始到结束可以走的最短**非空**路径的长度。如果没有这样的路径，输出一行，包含单词 "impossible"。 ### 样例输入 ``` 1 5 4 1 1 2 2 2 3 3 3 4 -3 4 5 -2 1 5 ``` ### 样例输出 ``` 4 ```