How do I show this variant of the longest path problem is NP-hard?
Hint 1. The graph doesn't have to be connected.

Hint 2. Mouse-over the following for a slightly more detailed hint.


   Arrange for there to be two components. One of them has quite a long path, which you can easily find.