You might want to think carefully about MEL-PHE-MEL. There is only one direct flight per week in each direction, both on Tuesdays, and the timings do not allow a turnaround in PHE, so you would have to spend a week there, which, unless you want to go exploring the NW of WA, or you have friends there, would be very long time...although I must admit I have never been there myself. (The NW of WA is supposed to be quite spectacular.) Others may care to comment?