아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Imperfect Imperial Units

시간 제한4초메모리 제한1024 MB

요약
단위 변환 방정식들이 그래프를 이루고 있을 때, 한 단위의 값을 다른 단위로 변환하는 질의에 답하거나 불가능하다고 출력합니다.
난이도

보통10점 중 5점

유형
그래프, DFS, 구현
정답자
아직 제출이 없습니다

문제

You are writing a paper for the Beta Astronomy Physics Conference about your recent discovery on grey holes. One of your collaborators has performed a huge number of measurements, which you would like to analyse in order to draw some conclusions. The only problem is: the data is measured in a wide variety of units, and to your disgust, they appear to use a mix of the imperial and metric systems. To simplify your analysis, you need to convert all these measurements into a different unit.

입력

The input consists of:

  • One line with two integers nn and qq (1≤n≤1001\leq n\leq 100, 1≤q≤10,0001\leq q\leq 10\\,000), the number of unit conversion equations and the number of queries to answer.
  • nn lines, each defining a unit conversion in the format "1 <unit> = <value> <unit>".
  • qq lines, each with a query in the format "<value> <unit> to <unit>".

In these formats, "<value>" is a floating-point number vv (0.001≤v≤10000.001 \leq v \leq 1000, with at most 99 digits after the decimal point) and "<unit>" is a string of at most 2020 English lowercase letters (a-z). A unit in a query is guaranteed to be defined in at least one unit conversion equation. Every unit can be converted into every other unit in at most one way.

출력

For every query, output the value of the requested unit, or "impossible" if the query cannot be answered.

Your answers should have a relative error of at most 10−610^{-6}.

예제3

  1. 예제 1

    입력
    4 3
    1 foot = 12 inch
    1 yard = 3 foot
    1 meter = 100 centimeter
    1 centimeter = 10 millimeter
    750 millimeter to meter
    42 yard to inch
    10 meter to foot
    
    예상 출력
    0.75
    1512
    impossible
    
  2. 예제 2

    입력
    4 3
    1 fortnight = 14 day
    1 microcentury = 0.036525 day
    1 microcentury = 1000 nanocentury
    1 week = 7 day
    22.2 fortnight to nanocentury
    2.5 nanocentury to week
    3.14 day to fortnight
    
    예상 출력
    8509240.2464065708427
    1.3044642857142857142e-05
    0.22428571428571428572
    
  3. 예제 3

    입력
    10 2
    1 micrometer = 1000 nanometer
    1 millimeter = 1000 micrometer
    1 meter = 1000 millimeter
    1 kilometer = 1000 meter
    1 megameter = 1000 kilometer
    1 lightsecond = 299.792458 meter
    1 lightminute = 60 lightsecond
    1 lighthour = 60 lightminute
    1 lightday = 24 lighthour
    1 lightyear = 365.25 lightday
    42 nanometer to lightyear
    42 lightyear to nanometer
    
    예상 출력
    4.439403502903384947e-18
    3.9735067984839359997e+20