LQ 国拥有 n 个城市，从 0 到 n 1 编号，这 n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的，每条道路都有一个属性 D ，表示这条道路的灰尘度，当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。
LQ 国拥有 n 个城市，从 0 到 n − 1 编号，这 n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D ，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。 LQ 国很看重居民的出行环境，他们用一个指标 P 来衡量 LQ 国的出行环境，P 定义为： 其中 d(i, j) 表示城市 i 到城市 j 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1，但每条道路都有一个灰尘度的下限值 L，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。 具体的计划是这样的： 第 1 天，0 号城市对与其直接相连的道路环境进行改善； 第 2 天，1 号城市对与其直接相连的道路环境进行改善； … 第 n 天，n − 1 号城市对与其直接相连的道路环境进行改善； 第 n + 1 天，0 号城市对与其直接相连的道路环境进行改善； 第 n + 2 天，1 号城市对与其直接相连的道路环境进行改善； … LQ 国想要使得 P 指标满足 P ≤ Q。请问最少要经过多少天之后，P 指标可以满足 P ≤ Q。如果在初始时就已经满足条件，则输出 0 ；如果永远不可能满足，则输出 −1。
（图片来源网络，侵删）
