题目描述

你刚刚为新机器人搭建了一块电路板，现在需要为其供电。机器人电路由多个电子元件组成，每个元件都需要一定的电流才能工作。每个元件有一个正极（+）和一个负极（-）引脚，它们连接到电路板上的节点。电流从正极流向负极（但需注意，元件不会“消耗”电流：从正极流入的所有电流都会从负极流出）。

电路板上的节点标号为 (1, \dots, N)，除了两个特殊节点：标有 + 和 - 的电源端子。正极端子仅连接元件的正极引脚，负极端子仅连接元件的负极引脚。从连接元件负极引脚流入节点的所有电流，都会通过连接的正极引脚流出。你可以控制每个节点流向各正极引脚的电流量（尽管具体实现方法超出本题范围）。此外，已知电路中没有反馈回路（即元件不会形成允许电流循环流动的链式结构）。

图1：(a)中所有元件均可通过从正极到负极的有向路径供电；(b)中元件4和6无法供电，因为从节点4到负极没有有向路径。

为了节省电力并避免电路过热，你希望用尽可能小的电流让机器人正常工作。需要从正极端子输入的最小电流是多少（可以认为所有电流最终都会从负极端子流出），才能确保每个元件获得所需的工作电流？

输入

输入包含多个测试用例。每个测试用例以一行开头，包含两个整数：(N)（(0 \leq N \leq 50)，表示除正负极外的节点数）和 (M)（(1 \leq M \leq 200)，表示电路中的元件数）。接下来的 (M) 行描述每个元件，第 (i) 个元件的描述包含三个字段：(p_i)（元件连接的正极节点）、(n_i)（元件连接的负极节点）、整数 (I_i)（(1 \leq I_i \leq 100)，元件正常工作所需的最小电流）。节点 (p_i) 和 (n_i) 可以是字符 +（正极端子）、-（负极端子）或整数（(1) 到 (N) 之间的节点编号）。没有两个元件具有相同的正负极节点组合。输入以 (N = M = 0) 的无效用例结束，该用例无需处理。

输出

对于每个输入用例，你的程序应输出以下内容之一：

• 一个整数，表示为确保所有元件正常工作，必须从正极端子提供的最小电流；
• 若无法同时为所有元件提供足够电流，则输出消息 impossible。

输入示例 1

6 10  
+ 1 1  
1 2 1  
1 3 2  
2 4 5  
+ - 1  
4 3 2  
3 5 5  
4 6 2  
5 - 1  
6 5 3  
4 6  
+ 1 8  
1 2 4  
1 3 5  
2 4 6  
3 - 1  
3 4 3  
0 0  

输出示例 1

9  
impossible  

提示

对于熟悉电子学的读者，可以假设你能够调整每个元件的电位而不改变其电流需求，或者等效地，每个元件串联一个精确的可变电位器。电源将为电路提供足够的电位。

来源

Pacific Northwest 2008