领主也应在所有这些事情上，对忠诚的封臣履行相应的义务。
- 沙特尔的富尔贝，致阿基坦公爵威廉的信（1020年）
你是一名负责王国道路的官员，最近开始猖獗的拦路强盗让你十分头疼。为了解决这一问题，国王打算命令麾下的领主派出骑士，组建警卫队，维护道路的治安和安全。然而，每位领主能够派出的骑士人数不同，因此未必能为所有道路安排骑士。
王国有包括国王在内的 位领主，编号为 到 。 号领主是国王。除国王以外，每位领主恰好效忠于一位主君，并且是这位主君的封臣。从任意领主开始，不断沿着主君关系向上追溯，最终都能到达国王。
每位领主都统治着一块属于自己的土地，称为领地。 号领主的主君是 号领主，除国王以外，每位领主的领地与其主君的领地之间都有一条道路相连。
王国中也可能存在连接不具有主君与封臣关系的领主领地的道路。然而，国王希望优先保护主君与封臣之间的往来。因此，只能为连接各领主领地与其主君领地的道路安排警卫队。其他道路在本题中不予考虑。
每条道路的警卫队由两名骑士组成，由道路两端的领主各派出一名。 号领主能够派出 名骑士参与治安维护。每名骑士至多加入一支警卫队，每条道路至多安排一支警卫队。不必安排所有骑士。
安排了警卫队的道路就是安全的道路。求上述道路中安全道路条数的最大值。
第一行包含领主人数 。
第二行包含 ，以空格分隔。
输出安全道路条数的最大值。
第一个样例中，可以为 号与 号领地之间、 号与 号领地之间、 号与 号领地之间的道路安排警卫队。所有需要考虑的道路都与 号或 号领地相连，而这两位领主总共只能派出 名骑士，因此不可能为 条或更多道路安排警卫队。
第三行包含 ，以空格分隔。
第二个样例中，所有需要考虑的道路都与国王的领地相连。由于国王无法派出骑士，因此不能安排任何警卫队。
